你知道一些很好的Java库，可以让你生成两个（或更多）集合的笛卡尔积吗？
例如：我有三个集合。一个是类Person的对象，第二个是类Gift的对象，第三个是类GiftExtension的对象。
我想生成一个包含所有可能三元组Person-Gift-GiftExtension的集合。
集合的数量可能会有所变化，因此我不能在嵌套的foreach循环中执行此操作。 在某些条件下，我的应用程序需要生成Person-Gift对的乘积，有时是三元组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的cartesianProduct呢？
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]]);
}
}
}
这里有一个Iterator，它提供了一个二维数组的笛卡尔积，其中数组组件表示问题中的集合（可以将实际的Set转换为数组）：
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;
}
}
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]
这里有一个可迭代对象，它允许您使用简化的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。我们返回一个对象列表 - 这可以是Set而不是List，但Set没有索引访问，所以使用Set代替List会更加复杂。与通用解决方案不同的是，对于许多目的来说，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);
}
}
要实现 Iterable 接口，以便使用 for-each 循环，我们需要实现 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, )
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);
}
}
你可以使用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]
Set<List<Object>>，否则你可能会在结果中得到不同大小的集合（因为有重复项）。 - MarcocartesianProduct的参数更改为ArrayList，则返回的笛卡尔积将按相反的顺序返回。我的意思是，笛卡尔积的第一个元素将是给定的最后一个集合的元素。这是为什么？ - foobarArrayList<ArrayList<Double>>并以ArrayList<ArrayList<Double>>数据类型返回方法？当我进行修改时，笛卡尔积的顺序会发生变化。 - foobar