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 setA = new HashSet<>(Arrays.asList(10,20)); Set setB = new HashSet<>(Arrays.asList(“John”,“Jack”)); Set setC = new HashSet<>(Arrays.asList(‘I’,‘J’));

Set> cartesianProduct = new HashSet<>();
for (int i: setA) {
    for (String j: setB) {
        for (char k: setC) {
            List tuple = Arrays.asList(i,j,k);
            cartesianProduct.add(tuple);
        }
    }
}

for (List 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>, 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> sets = new ArrayList<>(); sets.add(List.of(10, 20)); sets.add(List.of(“John”, “Jack”)); sets.add(List.of(‘I’, ‘J’)); List> cartesianProduct = getCartesianProduct(sets); System.out.println(cartesianProduct); } public static List> getCartesianProduct(List> sets) { List> result = new ArrayList<>(); getCartesianProductHelper(sets, 0, new ArrayList<>(), result); return result; } private static void getCartesianProductHelper(List> sets, int index, List current, List> result) { if (index == sets.size()) { result.add(new ArrayList<>(current)); return; } List 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’re calculating the total number of possible combinations by using the bitwise shifting. For each specific combination, we’re using the binary representation of the combination index. This index allows us to decide which elements from the set should be included in the current 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> getCartesianProductIterative(List> sets) List> 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 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> getCartesianProductUsingStreams(List> sets) { return cartesianProduct(sets,0).collect(Collectors.toList()); } public Stream> cartesianProduct(List> sets, int index) { if (index == sets.size()) { List emptyList = new ArrayList<>(); return Stream.of(emptyList); } List currentSet = sets.get(index); return currentSet.stream().flatMap(element -> cartesianProduct(sets, index+1) .map(list -> { List 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:

com.google.guava
guava
32.1.1-jre

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> as an input and returns a set of lists Set> 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> getCartesianProductUsingGuava(List> sets) { Set> cartesianProduct = Sets.cartesianProduct(sets); List> 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. The complete source code for these examples is available over on GitHub.