1. Introduction
1.导言
In this tutorial, we’ll focus on the Cartesian product and how to get the Cartesian product of any number of sets in Java.
在本教程中，我们将重点介绍笛卡尔积以及如何用 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.
当您需要从多个集合中生成所有可能的元素排列和组合时，多个集合的笛卡尔乘积是 Java 中的一个有用概念。此操作常用于各种场景，如测试数据生成、数据库查询和游戏开发。
2. Cartesian Product
2.笛卡尔积
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:
让我们借助三个集合的例子来理解这一点：setA、setB 和 setC。我们将计算笛卡尔积，由此产生的 cartesianProduct 集将包含代表三个输入集笛卡尔积的所有有序元组：
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
3.使用普通 Java 获取笛卡尔积
In the following sections, we’ll look at the various ways (iterative, recursive, and using Java8 streams) to generate the Cartesian Product.
在接下来的章节中，我们将了解生成笛卡尔积的各种方法（迭代、递归和使用 Java8 流）。
3.1. Recursive Approach
3.1.递归方法
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:
我们可以使用递归方法在 Java 中计算任意数量集合的笛卡尔积。输出定义为 列表<List<Object>>，其中每个内部列表可以包含整数、字符串和字符的混合：
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
3.2.使用位操作的迭代法
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.
在下面的代码中，我们通过位移来计算可能组合的总数。总组合数的计算公式为 totalSets 的幂次 2。外循环至关重要，它使用二进制计数器 i 遍历所有可能的组合。</em
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.
在表达式 ((((i>>j) & 1) == 1) 中，我们使用了右移操作，提取 i 二进制表示中的 j 位。该位可帮助我们确定是否需要在组合中包含当前集合中的第一个或第二个元素。如果提取的位被置位（或等于 1），则会将集合中的第一个元素添加到组合中；否则，就会包含第二个元素。
For example: ((i >> j) & 1) is equivalent to ((0b0010 >> 0) & 1), which results in 0b0010 & 0b00001, equal to 0b0000 or 0.
例如((i >> j) & 1) 相当于 ((0b0010 >> 0) & 1)，结果是 0b0010 & 0b00001，等于 0b0000 或 0。
Therefore, the second element of Set 0 (sets.get(0).get(1)) is included in the combination.
因此，集合 0 的第二个元素 （sets.get(0).get(1)）包含在组合中。
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
3.3.使用数据流
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:
我们将使用 Java 8 流和递归调用来生成笛卡尔积。cartesianProduct方法将返回一个包含所有可能组合的流。基本情况是当索引达到 sets 的大小时，返回一个空列表以终止递归。让我们使用流来生成笛卡尔积：
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
4.使用 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:
Guava是由 Google 开发的一个流行库，它提供了处理集合的实用程序，包括计算多个集合的笛卡尔积。要使用 Guava 计算笛卡尔积，我们首先要在 pom.xml 中添加 Google Guava 库依赖关系：</em
<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:
现在，我们将使用 Guava 的 Set.cartesianProduct() 方法，该方法将集合 List<Set<Object>> 作为输入，并返回一组包含输入集合中所有元素组合的列表 Set<List<Object>> 。最后，我们将列表集转换为列表列表，并返回输出结果：
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
5.结论
In this article, we focused on various ways to calculate the Cartesian Product of any number of sets in Java.
在本文中，我们将重点介绍在 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.
其中一些方法是纯 Java 的，另一些则需要额外的库。每种方法都有自己的优势，用户可以根据具体的使用情况和性能要求来选择它们。递归方法简单明了，更容易理解，而迭代方法通常对较大的集合更有效。
The complete source code for these examples is available over on GitHub.
这些示例的完整源代码可在 GitHub 上获取。