Cartesian Product of Any Number of Sets in Java

1. Introduction

In this tutorial, we’ll focus on the Cartesian product and how to get the Cartesian product of any number of sets in Java.

The Cartesian product of multiple sets is a useful concept in Java when you need to generate all possible permutations and combinations of elements from those sets. This operation is commonly used in various scenarios, such as test data generation, database queries, and game development.

2. Cartesian Product

A Cartesian Product is a mathematical operation that combines the elements of multiple sets to create a new set, where each element in the new set is an ordered tuple containing one element from each input set. The size of the Cartesian product is equal to the product of the sizes of the input set.

Let’s understand this with the help of an example by using three sets: setA, setB, and setC. We’ll calculate the Cartesian Product, and the resulting cartesianProduct set will contain all the ordered tuples representing the Cartesian Product of the three input sets:

public void cartesianProduct() {
    Set<Integer> setA = new HashSet<>(Arrays.asList(10,20));
    Set<String> setB = new HashSet<>(Arrays.asList("John","Jack"));
    Set<Character> setC = new HashSet<>(Arrays.asList('I','J'));
    
    Set<List<Object>> cartesianProduct = new HashSet<>();

    for (int i: setA) {
        for (String j: setB) {
            for (char k: setC) {
                List<Object> tuple = Arrays.asList(i,j,k);
                cartesianProduct.add(tuple);
            }
        }
    }
    
    for (List<Object> tuple: cartesianProduct) {
        System.Out.Println(tuple);
    }
}

Here is the output of the above program:

[10,John,I]
[10,John,J]
[10,Jack,I]
[10,Jack,J]
[20,John,I]
[20,John,J]
[20,Jack,I]
[20,Jack,J]

Now, let’s look at the various approaches to calculating the Cartesian product of any number of sets.

3. Get Cartesian Product using Plain Java

In the following sections, we’ll look at the various ways (iterative, recursive, and using Java8 streams) to generate the Cartesian Product.

3.1. Recursive Approach

We can use a recursive approach to compute the Cartesian Product of any number of sets in Java. The output is defined as List<List<Object>>, where each inner list can contain a mix of integers, strings, and characters. Here is a sample code to achieve this:

public static void main(String args[]) {
    List<List<Object>> sets = new ArrayList<>();
    sets.add(List.of(10, 20));
    sets.add(List.of("John", "Jack"));
    sets.add(List.of('I', 'J'));
    List<List<Object>> cartesianProduct = getCartesianProduct(sets);
    System.out.println(cartesianProduct);
}

public static List<List<Object>> getCartesianProduct(List<List<Object>> sets) {
    List<List<Object>> result = new ArrayList<>();
    getCartesianProductHelper(sets, 0, new ArrayList<>(), result);
    return result;
}

private static void getCartesianProductHelper(List<List<Object>> sets, int index, List<Object> current, List<List<Object>> result) {
    if (index == sets.size()) {
        result.add(new ArrayList<>(current));
        return;
    }
    List<Object> currentSet = sets.get(index);
    for (Object element: currentSet) {
        current.add(element);
        getCartesianProductHelper(sets, index+1, current, result);
        current.remove(current.size() - 1);
    }
}

The output contains eight elements in the list:

[[10,John,I]
[10,John,J]
[10,Jack,I]
[10,Jack,J]
[20,John,I]
[20,John,J]
[20,Jack,I]
[20,Jack,J]]

3.2. Iterative Approach Using Bit Manipulation

In the following code, we calculate the total number of possible combinations by using the bitwise shifting. The totalCombinations are computed as 2 to the power of the totalSets. The outer loop is crucial, iterating through all possible combinations using a binary counter i.

In the expression (((i >> j) & 1) == 1) we’re using a right shift operation that extracts the j-th bit of the binary representation of i. This bit helps us to determine whether we need to include the first or second element from the current set in the combination. If the extracted bit is set (or equals 1), the first element from the set is added to the combination; otherwise, the second element is included.

For example: ((i >> j) & 1) is equivalent to ((0b0010 >> 0) & 1), which results in 0b0010 & 0b00001, equal to 0b0000 or 0.

Therefore, the second element of Set 0 (sets.get(0).get(1)) is included in the combination.

These formed combinations are then accumulated within the result list and ultimately returned as Cartesian Product. Let’s take a look at another approach where we try to generate the Cartesian Product using bit manipulation:

public List<List<Object>> getCartesianProductIterative(List<List<Object>> sets) {
    List<List<Object>> result = new ArrayList<>();
    if (sets == null || sets.isEmpty()) {
        return result;
    }
    int totalSets = sets.size();
    int totalCombinations = 1 << totalSets;
    for (int i = 0; i < totalCombinations; i++) {
        List<Object> combination = new ArrayList<>();
        for (int j = 0; j < totalSets; j++) {
            if (((i >> j) & 1) == 1) {
                combination.add(sets.get(j).get(0));
            } else {
                combination.add(sets.get(j).get(1));
            }
        }
        result.add(combination);
    }
    return result;
}

Here is the output of the above program:

[20, Jack, J]
[10, Jack, J]
[20, John, J]
[10, John, J]
[20, Jack, I]
[10, Jack, I]
[20, John, I]
[10, John, I]

3.3. Using Streams

We’ll use Java 8 streams and recursive calls to generate the Cartesian Product. The cartesianProduct method will return a stream of all possible combinations. The base case is when the index reaches the size of the sets, and an empty list is returned to terminate the recursion. Let’s use streams to generate the Cartesian Product:

public List<List<Object>> getCartesianProductUsingStreams(List<List<Object>> sets) {
    return cartesianProduct(sets,0).collect(Collectors.toList());
}

public Stream<List<Object>> cartesianProduct(List<List<Object>> sets, int index) {
    if (index == sets.size()) {
        List<Object> emptyList = new ArrayList<>();
        return Stream.of(emptyList);
    }
    List<Object> currentSet = sets.get(index);
    return currentSet.stream().flatMap(element -> cartesianProduct(sets, index+1)
      .map(list -> {
          List<Object> newList = new ArrayList<>(list);
          newList.add(0, element);
          return newList;
      }));
}

Here is the output of the above program:

[10,John,I]
[10,John,J]
[10,Jack,I]
[10,Jack,J]
[20,John,I]
[20,John,J]
[20,Jack,I]
[20,Jack,J]

4. Get Cartesian Product using Guava

Guava, which is a popular library developed by Google, provides utilities to work with collections, including computing the Cartesian Product of multiple sets. To use Guava for computing the Cartesian Product, let’s start by adding Google’s Guava library dependency in pom.xml:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.0.0-jre</version>
</dependency>

The latest version of the dependency can be checked here.

Now, we’ll use Guava’s Set.cartesianProduct() method, which takes a list of sets List<Set<Object>> as an input and returns a set of lists Set<List<Object>> containing all the combinations of elements from the input sets. Finally, we transformed the set of lists into a list of lists and returned the output:

public List<List<Object>> getCartesianProductUsingGuava(List<Set<Object>> sets) {
    Set<List<Object>> cartesianProduct = Sets.cartesianProduct(sets);
    List<List<Object>> cartesianList = new ArrayList<>(cartesianProduct);
    return cartesianList;
}

The output contains eight elements in the list:

[[10,John,I]
[10,John,J]
[10,Jack,I]
[10,Jack,J]
[20,John,I]
[20,John,J]
[20,Jack,I]
[20,Jack,J]]

5. Conclusion

In this article, we focused on various ways to calculate the Cartesian Product of any number of sets in Java.

While some of them were purely Java, others required additional libraries. Each method has its advantages, and users may prefer them based on the specific use case and performance requirements. The recursive approach is straightforward and easier to understand, while the iterative approach is generally more efficient for larger sets.