How to Compute the Cartesian Product of an Arbitrary Number of Sets in Java?

Cartesian Product of an Arbitrary Number of Sets in Java

When dealing with multiple sets, a common operation is computing their cartesian product, which generates a set containing all possible combinations of elements from the input sets. To facilitate this in Java, let's explore a solution that handles an arbitrary number of sets.

Recursive Approach for Cartesian Product

The following recursive Java method, cartesianProduct, calculates the cartesian product of any 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);
}

The recursive helper method, _cartesianProduct, constructs the cartesian product by iteratively adding elements from each set to the accumulating 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;
}

Example Usage

To demonstrate the usage of this method, consider the example provided in the question, where we have three sets containing objects of classes Person, Gift, and GiftExtension. We can obtain the cartesian product of these sets as follows:

Set<Person> persons = ...;
Set<Gift> gifts = ...;
Set<GiftExtension> giftExtensions = ...;

Set<Set<Object>> cartesianProduct = cartesianProduct(persons, gifts, giftExtensions);

The resulting cartesianProduct will contain sets representing all possible combinations of persons, gifts, and gift extensions.

Generic Type Information

It's important to note that Java's type system doesn't allow for methods to return generic types with an arbitrary number of parameters. This means that the cartesianProduct method returns Set>, regardless of the types of elements in the input sets.

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