How to Efficiently Compute the Cartesian Product of Multiple Sets in Java?

Computing Cartesian Product of Multiple Sets in Java

In Java, calculating the Cartesian product of two or more sets is a common operation. This involves generating a new set that contains all possible combinations of elements from the input sets.

A Recursive Solution

Traditional approaches using nested loops can become cumbersome when dealing with an arbitrary number of sets. Instead, consider a recursive approach:

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<>();
    if (index == sets.length) {
        ret.add(new HashSet<>());
    } else {
        for (Object obj : sets[index]) {
            for (Set<Object> set : _cartesianProduct(index + 1, sets)) {
                set.add(obj);
                ret.add(set);
            }
        }
    }
    return ret;
}

Considerations

Note that this recursive implementation loses generic type information due to limitations in Java's generic parameter system. To preserve type information, consider defining a specific tuple class for the number of sets involved, such as Triple for three sets. However, this approach is impractical for an arbitrary number of sets.

The above is the detailed content of How to Efficiently Compute the Cartesian Product of Multiple Sets in Java?. For more information, please follow other related articles on the PHP Chinese website!