1. 概述
本文重点介绍笛卡尔积的概念，以及如何在Java中获取任意数量集合的笛卡尔积。
当需要从集合中生成所有可能的元素排列和组合时，笛卡尔积非常有用。它常见于测试数据生成、数据库查询和游戏开发等场景。
2. 笛卡尔积
笛卡尔积是一种数学运算，通过组合多个集合的元素创建一个新的集合，新集合中的每个元素都是一个包含输入集合每个元素的有序元组。笛卡尔积的大小等于输入集合大小的乘积。
下面例子中，我们有3个集合 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);
}
}
以下是上述程序的输出：
[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层循环完成了任务。如果是4个、5个甚至更多数量的集合呢？
接下来，我们将介绍多种方法计算 任意数量 集合的笛卡尔积。
3. 使用纯Java获取笛卡尔积
方法一，我们在不借助第三方库的情况使用原生Java，通过迭代、递归和 Java Stream 方法来生成笛卡尔积。
3.1. 递归方法
在Java中，我们可以使用递归方法计算任意数量集合的笛卡尔积。输出定义为List<List<Object>>，其中每个内部List可以包含整数、字符串和字符的混合。 以下是一个实现此功能的示例代码：
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);
}
}
输出列表包含8个元素：
[[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. 使用位操作的迭代方法
在下面的代码中，我们通过位操作计算所有可能组合的数量。totalCombinations由所有集合的总数的2次方计算得出。外部循环使用二进制计数器i遍历所有可能的组合。
表达式((i >> j) & 1) == 1使用了右移操作（/java-bitwise-operators#2-signed-right-shift-gtgt），从i的二进制表示中提取第j位。这个位帮助我们确定是否在组合中包含第一个或第二个集合元素。如果提取的位设置（等于1），则在组合中添加第一个元素；否则，添加第二个元素。
例如：((i >> j) & 1)相当于((0b0010 >> 0) & 1)，结果为0b0000或0。
因此，从集合0的第二个元素（sets.get(0).get(1)）开始构建组合。
形成的组合被积累到结果列表中，并最终作为笛卡尔积返回。让我们看看另一种使用位操作生成笛卡尔积的方法：
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;
}
以下是上述程序的输出：
[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. 使用Java 8流
我们将使用Java 8 Stream和递归调用来生成笛卡尔积。cartesianProduct方法将返回所有可能组合的Stream。当index达到sets的大小时，返回一个空List以终止递归：
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;
}));
}
上述程序的输出：
[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. 使用Guava获取笛卡尔积
Google 开源的Guava库提供了处理集合的工具，包括计算多个集合的笛卡尔积。要在Guava中计算笛卡尔积，请首先在pom.xml中添加Google Guava库依赖：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>33.0.0-jre</version>
</dependency>
您可以在此处查看最新版本的依赖：https://mvnrepository.com/artifact/com.google.guava/guava
现在，我们将使用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;
}
输出列表包含8个元素：
[[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. 总结
在这篇文章中，我们关注了Java中计算任意数量集合的笛卡尔积的多种方法。虽然有些方法纯用Java实现，但其他方法需要额外的库。每种方法都有其优势，用户可能会根据具体应用场景和性能需求选择它们。递归方法简单易懂，而迭代方法通常对大型集合更有效率。
完整的代码示例可在GitHub上找到：https://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-collections-set-2。