你知道一些简洁的 Java 库，它们可以让你制作两个（或更多）集合的笛卡尔积吗？
例如：我有三套。一个是 Person 类的对象，第二个是 Gift 类的对象，第三个是 GiftExtension 类的对象。
我想生成一组包含所有可能的三元组 Person-Gift-GiftExtension。
集合的数量可能会有所不同，因此我无法在嵌套的 foreach 循环中执行此操作。在某些情况下，我的应用程序需要制作 Person-Gift pair 的乘积，有时它是三重 Person-Gift-GiftExtension，有时甚至可能会设置 Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension 等。
编辑：删除了两组以前的解决方案。有关详细信息，请参阅编辑历史记录。
这是一种对任意数量的集合递归执行的方法：
public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
if (sets.length < 2)
throw new IllegalArgumentException(
"Can't have a product of fewer than two sets (got " +
sets.length + ")");
return _cartesianProduct(0, sets);
}
private static Set<Set<Object>> _cartesianProduct(int index, Set<?>... sets) {
Set<Set<Object>> ret = new HashSet<Set<Object>>();
if (index == sets.length) {
ret.add(new HashSet<Object>());
} else {
for (Object obj : sets[index]) {
for (Set<Object> set : _cartesianProduct(index+1, sets)) {
set.add(obj);
ret.add(set);
}
}
}
return ret;
}
请注意，不可能在返回的集合中保留任何通用类型信息。如果您事先知道要获取多少个集合的乘积，则可以定义一个通用元组来保存那么多元素（例如Triple<A, B, C>），但是在 Java 中没有办法拥有任意数量的通用参数。
这是一个很老的问题，但为什么不使用Guava 的笛卡尔产品呢？
下面的方法创建字符串列表的笛卡尔积：
protected <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
List<List<T>> resultLists = new ArrayList<List<T>>();
if (lists.size() == 0) {
resultLists.add(new ArrayList<T>());
return resultLists;
} else {
List<T> firstList = lists.get(0);
List<List<T>> remainingLists = cartesianProduct(lists.subList(1, lists.size()));
for (T condition : firstList) {
for (List<T> remainingList : remainingLists) {
ArrayList<T> resultList = new ArrayList<T>();
resultList.add(condition);
resultList.addAll(remainingList);
resultLists.add(resultList);
}
}
}
return resultLists;
}
例子：
System.out.println(cartesianProduct(Arrays.asList(Arrays.asList("Apple", "Banana"), Arrays.asList("Red", "Green", "Blue"))));
会产生这个：
[[Apple, Red], [Apple, Green], [Apple, Blue], [Banana, Red], [Banana, Green], [Banana, Blue]]
集合的数量可能会有所不同，因此我无法在嵌套的 foreach 循环中执行此操作。
两个提示：
基于索引的解决方案
使用索引是一种快速且节省内存的替代方法，并且可以处理任意数量的集合。实现 Iterable 允许在 for-each 循环中轻松使用。有关用法示例，请参见#main 方法。
public class CartesianProduct implements Iterable<int[]>, Iterator<int[]> {
private final int[] _lengths;
private final int[] _indices;
private boolean _hasNext = true;
public CartesianProduct(int[] lengths) {
_lengths = lengths;
_indices = new int[lengths.length];
}
public boolean hasNext() {
return _hasNext;
}
public int[] next() {
int[] result = Arrays.copyOf(_indices, _indices.length);
for (int i = _indices.length - 1; i >= 0; i--) {
if (_indices[i] == _lengths[i] - 1) {
_indices[i] = 0;
if (i == 0) {
_hasNext = false;
}
} else {
_indices[i]++;
break;
}
}
return result;
}
public Iterator<int[]> iterator() {
return this;
}
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Usage example. Prints out
*
* <pre>
* [0, 0, 0] a, NANOSECONDS, 1
* [0, 0, 1] a, NANOSECONDS, 2
* [0, 0, 2] a, NANOSECONDS, 3
* [0, 0, 3] a, NANOSECONDS, 4
* [0, 1, 0] a, MICROSECONDS, 1
* [0, 1, 1] a, MICROSECONDS, 2
* [0, 1, 2] a, MICROSECONDS, 3
* [0, 1, 3] a, MICROSECONDS, 4
* [0, 2, 0] a, MILLISECONDS, 1
* [0, 2, 1] a, MILLISECONDS, 2
* [0, 2, 2] a, MILLISECONDS, 3
* [0, 2, 3] a, MILLISECONDS, 4
* [0, 3, 0] a, SECONDS, 1
* [0, 3, 1] a, SECONDS, 2
* [0, 3, 2] a, SECONDS, 3
* [0, 3, 3] a, SECONDS, 4
* [0, 4, 0] a, MINUTES, 1
* [0, 4, 1] a, MINUTES, 2
* ...
* </pre>
*/
public static void main(String[] args) {
String[] list1 = { "a", "b", "c", };
TimeUnit[] list2 = TimeUnit.values();
int[] list3 = new int[] { 1, 2, 3, 4 };
int[] lengths = new int[] { list1.length, list2.length, list3.length };
for (int[] indices : new CartesianProduct(lengths)) {
System.out.println(Arrays.toString(indices) //
+ " " + list1[indices[0]] //
+ ", " + list2[indices[1]] //
+ ", " + list3[indices[2]]);
}
}
}
这是一个 Iterable，它允许您使用简化的 for 循环：
import java.util.*;
// let's begin with the demo. Instead of Person and Gift,
// I use the well known char and int.
class CartesianIteratorTest {
public static void main (String[] args) {
List <Object> lc = Arrays.asList (new Object [] {'A', 'B', 'C', 'D'});
List <Object> lC = Arrays.asList (new Object [] {'a', 'b', 'c'});
List <Object> li = Arrays.asList (new Object [] {1, 2, 3, 4});
// sometimes, a generic solution like List <List <String>>
// might be possible to use - typically, a mixture of types is
// the common nominator
List <List <Object>> llo = new ArrayList <List <Object>> ();
llo.add (lc);
llo.add (lC);
llo.add (li);
// Preparing the List of Lists is some work, but then ...
CartesianIterable <Object> ci = new CartesianIterable <Object> (llo);
for (List <Object> lo: ci)
show (lo);
}
public static void show (List <Object> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o + ", ");
System.out.println (")");
}
}
它是如何完成的？我们需要一个 Iterable，以使用简化的 for 循环，并且必须从 Iterable 返回一个 Iterator。我们返回一个对象列表——这可以是一个集合而不是列表，但是集合没有索引访问，所以用集合而不是列表来实现它会有点复杂。与通用解决方案不同，Object 可以用于多种用途，但泛型允许更多限制。
class CartesianIterator <T> implements Iterator <List <T>> {
private final List <List <T>> lilio;
private int current = 0;
private final long last;
public CartesianIterator (final List <List <T>> llo) {
lilio = llo;
long product = 1L;
for (List <T> lio: lilio)
product *= lio.size ();
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private List<T> get (final int n, final List <List <T>> lili) {
switch (lili.size ())
{
case 0: return new ArrayList <T> (); // no break past return;
default: {
List <T> inner = lili.get (0);
List <T> lo = new ArrayList <T> ();
lo.add (inner.get (n % inner.size ()));
lo.addAll (get (n / inner.size (), lili.subList (1, lili.size ())));
return lo;
}
}
}
}
数学工作是在“get”方法中完成的。考虑 2 组 10 个元素。您总共有 100 种组合，从 00、01、02、... 10、... 到 99 枚举。对于 5 X 10 元素 50，对于 2 X 3 元素 6 组合。子列表大小的模有助于为每次迭代选择一个元素。
可迭代我这里最不有趣的事情：
class CartesianIterable <T> implements Iterable <List <T>> {
private List <List <T>> lilio;
public CartesianIterable (List <List <T>> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new CartesianIterator <T> (lilio);
}
}
为了实现允许for-each循环的Iterable，我们必须实现iterator()，而对于Iterator，我们必须实现hasNext()、next()和remove()。
结果：
(A, a, 1, )
(B, a, 1, )
(C, a, 1, )
(D, a, 1, )
(A, b, 1, )
(B, b, 1, )
(C, b, 1, )
(D, b, 1, )
...
(A, a, 2, )
...
(C, c, 4, )
(D, c, 4, )
这是一个Iterator给出二维数组的笛卡尔积的结果，其中数组组件表示问题中的集合（总是可以将实际Set的 s 转换为数组）：
public class CartesianIterator<T> implements Iterator<T[]> {
private final T[][] sets;
private final IntFunction<T[]> arrayConstructor;
private int count = 0;
private T[] next = null;
public CartesianIterator(T[][] sets, IntFunction<T[]> arrayConstructor) {
Objects.requireNonNull(sets);
Objects.requireNonNull(arrayConstructor);
this.sets = copySets(sets);
this.arrayConstructor = arrayConstructor;
}
private static <T> T[][] copySets(T[][] sets) {
// If any of the arrays are empty, then the entire iterator is empty.
// This prevents division by zero in `hasNext`.
for (T[] set : sets) {
if (set.length == 0) {
return Arrays.copyOf(sets, 0);
}
}
return sets.clone();
}
@Override
public boolean hasNext() {
if (next != null) {
return true;
}
int tmp = count;
T[] value = arrayConstructor.apply(sets.length);
for (int i = 0; i < value.length; i++) {
T[] set = sets[i];
int radix = set.length;
int index = tmp % radix;
value[i] = set[index];
tmp /= radix;
}
if (tmp != 0) {
// Overflow.
return false;
}
next = value;
count++;
return true;
}
@Override
public T[] next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
T[] tmp = next;
next = null;
return tmp;
}
}
基本思想是将count其视为多基数（数字i有自己的基数，等于i“第”组的长度）。每当我们必须解决next时（即，何时hasNext()被调用和next是null），我们将数字分解为这个多基数中的数字。这些数字现在用作我们从不同集合中提取元素的索引。
示例使用：
String[] a = { "a", "b", "c"};
String[] b = { "X" };
String[] c = { "r", "s" };
String[][] abc = { a, b, c };
Iterable<String[]> it = () -> new CartesianIterator<>(abc, String[]::new);
for (String[] s : it) {
System.out.println(Arrays.toString(s));
}
输出：
[a, X, r]
[b, X, r]
[c, X, r]
[a, X, s]
[b, X, s]
[c, X, s]
如果不喜欢数组，代码可以很容易地转换为使用集合。
我想这或多或少类似于“用户未知”给出的答案，只是没有递归和集合。
您可以使用Java 9 Streams获取任意数量的不同类型集合的笛卡尔积，并将其存储到一组对象中，如下所示：Set<Set<Object>>
public static Set<Set<Object>> cartesianProduct(Set<?>... sets) {
// incorrect incoming data
if (sets == null) return Collections.emptySet();
return Arrays.stream(sets)
// non-null and non-empty sets
.filter(set -> set != null && set.size() > 0)
// represent each set element as Set<Object>
.map(set -> set.stream().map(Set::<Object>of)
// Stream<Set<Set<Object>>>
.collect(Collectors.toSet()))
// summation of pairs of inner sets
.reduce((set1, set2) -> set1.stream()
// combinations of inner sets
.flatMap(inner1 -> set2.stream()
// merge two inner sets into one
.map(inner2 -> Stream.of(inner1, inner2)
.flatMap(Set::stream)
.collect(Collectors.toCollection(
LinkedHashSet::new))))
// set of combinations
.collect(Collectors.toCollection(LinkedHashSet::new)))
// returns Set<Set<Object>>, otherwise an empty set
.orElse(Collections.emptySet());
}
public static void main(String[] args) {
Set<Integer> set1 = Set.of(1, 2, 3);
Set<String> set2 = Set.of("A", "B", "C");
Set<Object> set3 = Set.of(new Time(0));
Set<Set<Object>> sets = cartesianProduct(set1, set2, set3);
// output
sets.forEach(System.out::println);
}
输出：
[1, A, 03:00:00]
[1, B, 03:00:00]
[1, C, 03:00:00]
[2, A, 03:00:00]
[2, B, 03:00:00]
[2, C, 03:00:00]
[3, A, 03:00:00]
[3, B, 03:00:00]
[3, C, 03:00:00]
一个简单的解决方案，例如对于整数集应该如下：
void printCombination(List<Set<Integer>> listSet, Set<Integer> combination) {
if (listSet.isEmpty()) {
System.out.println("a combination :" + combination);
return;
}
Set<Integer> intSet = listSet.get(0);
for (Integer it : intSet) {
Set<Integer> combination1 = new HashSet<Integer>();
combination1.addAll(combination);
combination1.add(it);
List<Set<Integer>> listSet1 = new ArrayList<Set<Integer>>();
listSet1.addAll(listSet);
listSet1.remove(0);
this.printCombination(listSet1, combination1);
}
}