Java 中任意數量集合的笛卡爾積
一、簡介
在本教程中，我們將重點介紹笛卡爾積以及如何在 Java 中獲取任意數量的集合的笛卡爾積。
當您需要從這些集合中生成所有可能的元素排列和組合時，多個集合的笛卡爾積在 Java 中是一個有用的概念。該操作常用於各種場景，例如測試數據生成、數據庫查詢、遊戲開發等。
2. 笛卡爾積
笛卡爾積是一種數學運算，它將多個集合的元素組合起來創建一個新集合，其中新集合中的每個元素都是一個有序元組，其中包含每個輸入集合中的一個元素。笛卡爾積的大小等於輸入集大小的乘積。
讓我們通過使用三個集合的示例來理解這一點： 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. 使用 Plain Java 獲取笛卡爾積
在以下部分中，我們將了解生成笛卡爾積的各種方法（迭代、遞歸和使用 Java8 流）。
3.1.遞歸方法
我們可以使用遞歸方法來計算 Java 中任意數量集合的笛卡爾積。輸出定義為List<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);
}
}輸出包含列表中的八個元素：
[[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.使用位操作的迭代方法
在下面的代碼中，我們使用按位移位來計算可能組合的總數。對於每個特定組合，我們使用組合索引的二進製表示形式。該索引允許我們決定集合中的哪些元素應包含在當前組合中。然後，這些形成的組合會在結果列表中累積，並最終作為笛卡爾積返回。
讓我們看一下另一種嘗試使用位操作生成笛卡爾積的方法：
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 流和遞歸調用來生成笛卡爾積。 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;
}));
}以下是上述程序的輸出：
[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 獲取笛卡爾積
Guava 是 Google 開發的一個流行庫，它提供了處理集合的實用程序，包括計算多個集合的笛卡爾積。要使用 Guava 計算笛卡爾積，我們首先在pom.xml:
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>32.1.1-jre</version>
</dependency>可以在此處檢查最新版本的依賴項。
現在，我們將使用 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;
}輸出包含列表中的八個元素：
[[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 上獲取。