Cartesian product of an arbitrary number of sets

by

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.

More Related Contents:

  1. Iteratively compute the Cartesian product of an arbitrary number of sets
  2. Cartesian product of streams in Java 8 as stream (using streams only)
  3. Removing duplicates from arraylist using set
  4. Obtaining a powerset of a set in Java
  5. How to convert an Array to a Set in Java
  6. Generate all combinations from multiple lists
  7. Java Set retain order?
  8. How to calculate the intersection of two sets? [duplicate]
  9. Getting an element from a Set
  10. What is the fastest way to compare two sets in Java?
  11. Different types of thread-safe Sets in Java
  12. Getting the difference between two sets
  13. What is the best way get the symmetric difference between two sets in java?
  14. Efficiently compute Intersection of two Sets in Java?
  15. Difference between Iterator and Listiterator?
  16. Why doesn’t java.util.Set have get(int index)?
  17. Removing items from a collection in java while iterating over it
  18. Any implementation of Ordered Set in Java?
  19. Changing HashMap keys during iteration
  20. Efficiently finding the intersection of a variable number of sets of strings
  21. Classical set operations for java.util.Collection
  22. Why does TreeSet throw a ClassCastException?
  23. HashSet contains duplicate entries
  24. How to set background image in Java?
  25. Why does my TreeSet not add anything beyond the first element?
  26. Issue with below snippet on boundary matchers regex (\b)
  27. How to Iterate over a Set/HashSet without an Iterator?
  28. Java HashSet with a custom equality criteria? [duplicate]
  29. Convert Set to HashMap
  30. Performance and Memory allocation comparison between List and Set

Leave a Comment