Cartesian Product of an Arbitrary Number of Sets

Cartesian product of an arbitrary number of sets

Edit: Previous solutions for two sets removed. See edit history for details.

Here is a way to do it recursively for an arbitrary number of sets:

public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
    if (sets.length < 2)
        throw new IllegalArgumentException(
                "Can't have a product of fewer than two sets (got " +
                sets.length + ")");

    return _cartesianProduct(0, sets);
}

private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
    Set<Set<Object>> ret = new HashSet<Set<Object>>();
    if (index == sets.length) {
        ret.add(new HashSet<Object>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Note that it is impossible to keep any generic type information with the returned sets. If you knew in advance how many sets you wanted to take the product of, you could define a generic tuple to hold that many elements (for instance Triple<A, B, C>), but there is no way to have an arbitrary number of generic parameters in Java.

Cartesian product of a variable number of sets each of variable size

Create an array with the maximum value per digit; in your example, that would be [2,3,4].

Set the maximum of digit j to 1, so you get [2,1,4].

Create a first combination [1,1,1] and add it to the result. Then repeatedly increment the combination and add it to the result.

To increment the combination, increment the last digit; if that digit equals the maximum, set it to 1 and increment the previous digit, and so on. If the first digit needs to be incremented and it's already set to the maximum value, you've found all combinations.

[1,1,1] -> [1,1,2] -> [1,1,3] -> [1,1,4] ->
4 is maximum for last digit, so set it to 1 and increment previous digit ->
1 is maximum for second digit, so set it to 1 and increment previous digit ->
[2,1,1] -> [2,1,2] -> [2,1,3] -> [2,1,4] ->
4 is maximum for last digit, so set it to 1 and increment previous digit ->
1 is maximum for second digit, so set it to 1 and increment previous digit ->
2 is maximum for first digit, so all combinations have been found.

Cartesian product of arbitrary number of arguments in python 3.6

To get the Cartesian product of all items of a list you can use the * operator to perform argument unpacking. This is sometimes known as "splat" unpacking.

from itertools import product

src = ['abc', '123',  'def']
cartesian_product = [''.join(t) for t in product(*src)]
print(cartesian_product)

output

['a1d', 'a1e', 'a1f', 'a2d', 'a2e', 'a2f', 'a3d', 'a3e', 'a3f', 'b1d', 'b1e', 'b1f', 'b2d', 'b2e', 'b2f', 'b3d', 'b3e', 'b3f', 'c1d', 'c1e', 'c1f', 'c2d', 'c2e', 'c2f', 'c3d', 'c3e', 'c3f']

Iteratively compute the Cartesian product of an arbitrary number of sets

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!

---

Related Topics