Kris Neuharth’s Blog

Finding Combinations Using Java

For a recent project at work I needed to generate all of the possible combinations of config parameters to be used in a parameter sweeping tool. We are using this tool to tune our software. When I first wrote the tool, the number of parameters was not changing so I could use the standard nested for-loop approach to iterate through all the lists of sweepable parameters and obtain all of the possible combinations easily.

In an effort to make the tool more flexible I needed to find a more dynamic way to iterate through all of the lists without the hard coded for-loops. I made some effort on my own but couldn’t produce the desired results fast enough. This seemed like a common enough problem that someone in the Java community may have already solved and published a solution for. Countless Google searches turned up only posts to development forums seeking the same answer I was.

Since I have been experimenting with Python off and on for the last year I decided to broaden my search to include the Python community. I quickly came across this example. The original author and commenters on that article present several approaches that leverage Python’s functional programming features which Java is begrudgedly unable to replicate. There was an example that looked like it could be ported to meet my needs because it was more straight forward and didn’t make use of Python’s bells and whistles.

Python code:

#!/usr/bin/env python

#Title: N-dimensional loop iterator
#Submitter: Philip Nunez
#Last Updated: 2001/11/01

#Description:
#Do nested for loops on an arbitrary list of iterable things.
#Found at: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/84739
class nloop:
    def __init__(self,*varg):
        self.list = list(varg)
        self.iter_list = []

        self.memo = [None] * len(self.list)
        if len(self.list):
            self.n_iter(0, self.list)

    def __getitem__(self,index):
        return self.iter_list[index]

    def n_iter(self,index,stack):
        x = stack[index]
        for i in x:
            self.memo[index] = i
            if index == len(stack) - 1:
                self.iter_list.append(tuple(self.memo))
            else:
                self.n_iter(index + 1, stack)

if __name__ == ‘__main__’:
    for tup in nloop(list(”abc”),
                     list(range(1,5)),
                     list(”def”),
                     list(range(5,10)),
                     list(”xyz”)):
        print tup

While Java doesn’t natively support the Python tuple data type, it looked easy enough to port to Java and begin using in my application. Without much trouble I was able to get a version working in Java that accomplished exactly what I needed to. I wrote it in a very generic way that attempted to mimic the Python code as closely as possible.

It is important to mention that I was generating the combinations from lists containing only strings. In order to use this code with other data types more work will probably need to be done. This code is obviously not the best and uses untyped collections but it was good enough for me for this particular tool.

Java code:

package com.krisneuharth.examples;

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("unchecked")

// Author: Kris Neuharth
// Ported directly from Python source found at:
// http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/84739
// Tried to keep it as close to the original and generic as possible
public class LoopIterator
{
	// Initialize generic lists
	List list;
	List iter_list;
	List memo;

	// Constructor
	public LoopIterator(List lol)
	{
		// Initialize lists
		this.list = lol;
		this.iter_list = new ArrayList();

		// Find number of expected values
		int expected = 1;
		for(Object list : this.list)
			expected *= ((List)list).size();

		// Test
		if(false)
		{
			System.out.println("\n-- Loop Iterator --");
			System.out.println("Size: " + this.list.size());
			System.out.println("Contents: " + this.list.toString());
			System.out.println("Expected Combinations: " + expected + "\n");
		}

		// Create buffer as big as list of lists, init elements to null
		this.memo = new ArrayList();
		for(int ii = 0; ii < this.list.size(); ii++)
			this.memo.add(ii, null);

		// If the list of lists has more than one list,
		// process it
		if(this.list.size() > 0)
			n_iter(0, this.list);
	}

	// Recursive method to generate combinations from all lists
	public void n_iter(int index, List> stack)
	{
		List x = stack.get(index);

		for(String i : x)
		{
			this.memo.set(index, i);
			if(index == stack.size() - 1)
				this.iter_list.add(new ArrayList(this.memo));
			else
				this.n_iter(index + 1, stack);
		}
	}

	// Utility method to display the combinations
	public void display()
	{
		int ii = 1;
		for(Object str : this.iter_list)
		{
			System.out.println((ii++) + "\t" +  str.toString());
		}
	}

        // Utility method to get the list of combinations for further
	// processing
	public List getCombinations()
	{
		return this.iter_list;
	}

	// Driver
	public static void main(String[] args)
	{
		// Create data
		List list1 = new ArrayList();
		list1.add(”a”);
		list1.add(”b”);
		list1.add(”c”);

		List list2 = new ArrayList();
		list2.add(”1″);
		list2.add(”2″);
		list2.add(”3″);

		List list3 = new ArrayList();
		list3.add(”w”);
		list3.add(”x”);
		list3.add(”y”);

		List list4 = new ArrayList();
		list4.add(”4″);
		list4.add(”5″);
		list4.add(”6″);

		// Create list of lists
		List lol = new ArrayList();
		lol.add(list1);
		lol.add(list2);
		lol.add(list3);
		lol.add(list4);

		// Create loop iterator
		LoopIterator li = new LoopIterator(lol);

		// Display results
		for(Object obj : li.getCombinations())
		{
			for(Object oj : (ArrayList)obj)
				System.out.print(oj + ” “);
			System.out.println();
		}
	}
}

I hope this was helpful to anyone else looking for a way to do this.