Java : Cartesian Product of a List of Lists
Try something like this:
public static void generate(int[][] sets) {
int solutions = 1;
for(int i = 0; i < sets.length; solutions *= sets[i].length, i++);
for(int i = 0; i < solutions; i++) {
int j = 1;
for(int[] set : sets) {
System.out.print(set[(i/j)%set.length] + " ");
j *= set.length;
}
System.out.println();
}
}
public static void main(String[] args) {
generate(new int[][]{{1,2,3}, {3,2}, {5,6,7}});
}
which will print:
1 3 5
2 3 5
3 3 5
1 2 5
2 2 5
3 2 5
1 3 6
2 3 6
3 3 6
1 2 6
2 2 6
3 2 6
1 3 7
2 3 7
3 3 7
1 2 7
2 2 7
3 2 7
I've implemented the algorithm above based on (I believe) one of Knuth's TAOCP books (in the comments @chikitin has a more specific reference: it is in PRE FASCICLE 2A section 7.2.1.1 Generating All n-tuple, of The Art Of Computer Programming by Knuth, Addison Wesley).
Note that I've named the arrays set, but they needn't hold unique elements, of course. The time I used it, they did contain unique elements, hence the name.
EDIT
It's pretty much a 1-on-1 translation:
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Vector;
public class Foo {
private LinkedHashMap<String, Vector<String>> dataStructure;
public Foo(LinkedHashMap<String, Vector<String>> dataStructure){
this.dataStructure = dataStructure;
}
public String[][] allUniqueCombinations(){
int n = dataStructure.keySet().size();
int solutions = 1;
for(Vector<String> vector : dataStructure.values()) {
solutions *= vector.size();
}
String[][] allCombinations = new String[solutions + 1][];
allCombinations[0] = dataStructure.keySet().toArray(new String[n]);
for(int i = 0; i < solutions; i++) {
Vector<String> combination = new Vector<String>(n);
int j = 1;
for(Vector<String> vec : dataStructure.values()) {
combination.add(vec.get((i/j)%vec.size()));
j *= vec.size();
}
allCombinations[i + 1] = combination.toArray(new String[n]);
}
return allCombinations;
}
public static void main(String[] args) {
LinkedHashMap<String, Vector<String>> data = new LinkedHashMap<String, Vector<String>>();
data.put("foo", new Vector<String>(Arrays.asList("1", "2", "3")));
data.put("bar", new Vector<String>(Arrays.asList("3", "2")));
data.put("baz", new Vector<String>(Arrays.asList("5", "6", "7")));
Foo foo = new Foo(data);
for(String[] combination : foo.allUniqueCombinations()) {
System.out.println(Arrays.toString(combination));
}
}
}
If you run the class above, the following is printed:
[foo, bar, baz]
[1, 3, 5]
[2, 3, 5]
[3, 3, 5]
[1, 2, 5]
[2, 2, 5]
[3, 2, 5]
[1, 3, 6]
[2, 3, 6]
[3, 3, 6]
[1, 2, 6]
[2, 2, 6]
[3, 2, 6]
[1, 3, 7]
[2, 3, 7]
[3, 3, 7]
[1, 2, 7]
[2, 2, 7]
[3, 2, 7]
How about generating the product lazily, ie. only create the tuple when you're accessing it?
/**
* A random access view of tuples of a cartesian product of ArrayLists
*
* Orders tuples in the natural order of the cartesian product
*
* @param T the type for both the values and the stored tuples, ie. values of the cartesian factors are singletons
* While the type of input sets is List<T> with elements being treated as singletons
*
*/
abstract public class CartesianProductView<T> extends AbstractList<T> {
private final List<List<T>> factors;
private final int size;
/**
* @param factors the length of the factors (ie. the elements of the factors argument) should not change,
* otherwise get may not return all tuples, or throw exceptions when trying to access the factors outside of range
*/
public CartesianProductView(List<List<T>> factors) {
this.factors = new ArrayList<>(factors);
Collections.reverse(this.factors);
int acc = 1;
for (Iterator<List<T>> iter = this.factors.iterator(); iter.hasNext(); ) {
acc *= iter.next().size();
}
this.size = acc;
}
@Override
public T get(int index) {
if (index < 0 || index >= size()) {
throw new IndexOutOfBoundsException(String.format("index %d > size() %d", index, size()));
}
T acc = null;
for (Iterator<List<T>> iter = factors.iterator(); iter.hasNext();) {
List<T> set = iter.next();
acc = makeTupleOrSingleton(set.get(index % set.size()), acc);
index /= set.size();
}
return acc;
}
@Override
public int size() {
return size;
}
private T makeTupleOrSingleton(T left, T right) {
if (right == null) {
return left;
}
return makeTuple(left, right);
}
/**
*
* @param left a singleton of a value
* @param right a tuple of values taken from the cartesian product factors, with null representing the empty set
* @return the sum of left and right, with the value of left being put in front
*/
abstract protected T makeTuple(T left, T right);
}
and use it like this
final List<List<String>> l1 = new ArrayList<List<String>>() {{ add(singletonList("a")); add(singletonList("b")); add(singletonList("c")); }};
final List<List<String>> l2 = new ArrayList<List<String>>() {{ add(singletonList("X")); add(singletonList("Y")); }};
final List<List<String>> l3 = new ArrayList<List<String>>() {{ add(singletonList("1")); add(singletonList("2")); add(singletonList("3")); add(singletonList("4")); }};
List<List<List<String>>> in = new ArrayList<List<List<String>>>() {{ add(l1); add(l2); add(l3); }};
List<List<String>> a = new CartesianProductView<List<String>>(in) {
@Override
protected List<String> makeTuple(final List<String> left, final List<String> right) {
return new ArrayList<String>() {{ add(left.get(0)); addAll(right); }};
}
};
System.out.println(a);
The result:
[[a, X, 1], [a, X, 2], [a, X, 3], [a, X, 4], [a, Y, 1], [a, Y, 2], [a, Y, 3], [a, Y, 4], [b, X, 1], [b, X, 2], [b, X, 3], [b, X, 4], [b, Y, 1], [b, Y, 2], [b, Y, 3], [b, Y, 4], [c, X, 1], [c, X, 2], [c, X, 3], [c, X, 4], [c, Y, 1], [c, Y, 2], [c, Y, 3], [c, Y, 4]]
As an added bonus, you can use it join strings all with all:
final List<String> l1 = new ArrayList<String>() {{ add("a"); add("b"); add("c"); }};
final List<String> l2 = new ArrayList<String>() {{ add("X"); add("Y"); }};
final List<String> l3 = new ArrayList<String>() {{ add("1"); add("2"); add("3"); add("4"); }};
List<List<String>> in = new ArrayList<List<String>>() {{ add(l1); add(l2); add(l3); }};
List<String> a = new CartesianProductView<String>(in) {
@Override
protected String makeTuple(String left, String right) {
return String.format("%s%s", left, right);
}
};
System.out.println(a);
The result:
[aX1, aX2, aX3, aX4, aY1, aY2, aY3, aY4, bX1, bX2, bX3, bX4, bY1, bY2, bY3, bY4, cX1, cX2, cX3, cX4, cY1, cY2, cY3, cY4]
Guava has a utility method which returns a cartesian product of the given list of sets: Sets.cartesianProduct.