Iteratively compute the Cartesian product of an arbitrary number of sets

Question

I want to compute the cartesian product of an arbitrary number of nonempty sets in Java.

I've wrote that iterative code...

public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {     List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());     List<T> elements = new ArrayList<T>(list.size());     List<Set<T>> toRet = new ArrayList<Set<T>>();     for (int i = 0; i < list.size(); i++) {         iterators.add(list.get(i).iterator());         elements.add(iterators.get(i).next());     }     for (int j = 1; j >= 0;) {         toRet.add(Sets.newHashSet(elements));         for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {             iterators.set(j, list.get(j).iterator());             elements.set(j, iterators.get(j).next());         }         elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());     }     return toRet; } 

...but I found it rather inelegant. Someone has a better, still iterative solution? A solution that uses some wonderful functional-like approach? Otherwise... suggestion about how to improve it? Errors?

Answer 1

I've written a solution that doesn't require you to fill up a large collection in memory. Unfortunately, the code required is hundreds of lines long. You may have to wait until it appears in the Guava project (https://github.com/google/guava), which I hope will be by the end of the year. Sorry. :(

Note that you may not need such a utility if the number of sets you're cartesian-producting is a fixed number known at compile time -- you could just use that number of nested for loops.

EDIT: the code is released now.

Sets.cartesianProduct()

I think you'll be very happy with it. It only creates the individual lists as you ask for them; doesn't fill up memory with all MxNxPxQ of them.

If you want to inspect the source, it's here.

Enjoy!

Answer 2

Using Google Guava 19 and Java 8 is very simple:

Say you have the List of all arrays you want to associate...

public static void main(String[] args) {   List<String[]> elements = Arrays.asList(     new String[]{"John", "Mary"},      new String[]{"Eats", "Works", "Plays"},     new String[]{"Food", "Computer", "Guitar"}   );    // Create a list of immutableLists of strings   List<ImmutableList<String>> immutableElements = makeListofImmutable(elements);    // Use Guava's Lists.cartesianProduct, since Guava 19   List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements);    System.out.println(cartesianProduct); } 

The method to make the list of immutable lists is as follows:

/**  * @param values the list of all profiles provided by the client in matrix.json  * @return the list of ImmutableList to compute the Cartesian product of values  */ private static List<ImmutableList<String>> makeListofImmutable(List<String[]> values) {   List<ImmutableList<String>> converted = new LinkedList<>();   values.forEach(array -> {     converted.add(ImmutableList.copyOf(array));   });   return converted; } 

The output is as follows:

[   [John, Eats, Food], [John, Eats, Computer], [John, Eats, Guitar],   [John, Works, Food], [John, Works, Computer], [John, Works, Guitar],    [John, Plays, Food], [John, Plays, Computer], [John, Plays, Guitar],   [Mary, Eats, Food], [Mary, Eats, Computer], [Mary, Eats, Guitar],   [Mary, Works, Food], [Mary, Works, Computer], [Mary, Works, Guitar],   [Mary, Plays, Food], [Mary, Plays, Computer], [Mary, Plays, Guitar] ]