Java中任意集合的笛卡尔积

你知道一些整洁的Java库吗，让你做两个（或更多）集的笛卡尔积？

例如：我有三套。 一个具有Person类的对象，其次是具有类Gift的对象，另一个具有类GiftExtension的对象。

我想生成一个包含所有可能的三元组Person-Gift-GiftExtension的集合。

集的数量可能会有所不同，所以我不能在嵌套的foreach循环中做到这一点。 在某些情况下，我的应用程序需要制作一个Person-Gift对的产品，有时候它是三倍的Person-Gift-GiftExtension，有时候甚至可能会设置Person-Gift-GiftExtension-GiftSecondExtension-GiftThirdExtension等。

Answer 1

编辑：删除了两套的以前的解决scheme。 详情请参阅编辑logging。

这是recursion地执行任意数量集合的一种方法：

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; } 

请注意，使用返回的集合保留任何genericstypes信息是不可能的。 如果事先知道有多less组需要使用该产品，则可以定义一个通用元组来保存许多元素（例如Triple<A, B, C> ），但是没有办法拥有任意数字Java中的generics参数。

Answer 2

下面的方法创build了string列表的笛卡尔积：

 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]] 

Answer 3

这是一个相当古老的问题，但为什么不使用番石榴的笛卡尔产品 ？

Answer 4

集的数量可能会有所不同，所以我不能在嵌套的foreach循环中做到这一点。

两个提示：

• A×B×C = A×（B×C）
• recursion

Answer 5

基于索引的解决scheme

使用索引是一种快速和高效的替代方法，可以处理任意数量的集合。 实现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]]); } } } 

Answer 6

这里是一个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返回。 我们返回一个对象列表 – 这可能是一个Set而不是List，但是Set没有索引访问，所以用Set而不是List来实现它会复杂一点。 Object不是一个通用的解决scheme，但对于许多目的来说，它可能是很好的，但是generics允许有更多的限制。

 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; } } } } 

math工作是在“get”方法中完成的。 考虑两套10个元素。 总共有100个组合，枚举从00,01,02,10 …到99.对于5 ​​X 10个元素50，对于2 X 3个元素6个组合。 子列表大小的模有助于为每次迭代select一个元素。

Iterable我最不感兴趣的是：

 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-eachtypes的循环，我们必须实现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, ) 

Answer 7

是的，有function的Java 。

一组：

s.bind（P.p2（），s）;

Answer 8

笛卡尔产品所需的内存（和处理）占用空间很快就会失控。 天真的执行会耗尽内存并花费大量的时间。 知道你计划在这样一个集合中执行的操作是很好的，以便提出一个实现策略。

无论如何，在Google集合上执行诸如Sets.SetView之类的操作。 这是一个由其他集合支持的集合，因为它们被添加。 他们的问题的想法是避免addAll调用。 你的问题的想法是避免使NxMxK添加到一个集合。

Google集合可以在这里find ，所提到的类在这里

Answer 9

下面是一个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; } } 

基本思想是把count一个多基数（数字i有自己的基数，等于第i个“set”的长度）。 无论何时我们必须解决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] 

如果不喜欢数组，代码可以转换为使用集合。

我想这或多或less类似于“用户未知”给出的答案，只有没有recursion和集合。