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 上獲取。