笛卡尔的产品的任意组在Java
https://stackoverflow.com/questions/714108
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
你知道一些整Java的方法，让你做笛卡尔的产品的两个(或更多)？
例如：我有三个集。一个与目的类人员，与第二类的对象的礼品以及第三类的对象的GiftExtension.
我希望产生一套包含所有可能三个人的礼物-GiftExtension.
集的数量可能有所不同所以我不能做这个套foreach循环。在某些条件下我的应用需要让产品的个人礼物对，有时候这是三个人的礼物-GiftExtension，有时甚至可能设置的个人的礼物-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的泛型参数的任意数。
其他提示
这是一个很老的问题，但为什么不使用的番石榴的笛卡儿积？
下面的方法创建的字符串列表的列表的笛卡尔乘积：
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循环中进行此操作。
两个提示：
- A x B x C = A x (B x C)
- 递归
<强>基于索引的溶液
与索引工作是速度快，存储器效率和可以处理任何数量组的一种替代方法。实现可迭代允许在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]]);
}
}
}
下面是一种可迭代，它允许使用一个简化的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 (")");
}
}
它是如何做呢？我们需要一个可迭代，使用简化的for循环和迭代，必须从可迭代返回。 我们返回对象的列表 - 这可能是一组，而不是名单，但设置没有索引访问，所以这将是一个比较复杂一点，有集，而不是列表来实现它。相反，一个通用的解决方案，目的可能是精细了很多用途，但仿制药允许更多的限制。
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×10元件50，为2 X 3元件6个的组合。子列表大小的模帮助挑选一个元素每次迭代。
可迭代I的最低有趣的事情在这里：
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，这允许换每个类型的循环中，我们必须实现迭代器（），以及用于迭代我们必须实现hasNext（），next（）和删除（）。
结果：
(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, )
下面是给出一个二维阵列，其中阵列的组件代表从问题的集合（一个总是可以转换实际Iterators到阵列）的笛卡尔乘积的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'th“组”的长度）。每当我们有解决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]
如果一个不喜欢阵列，代码是平凡转换为使用集合
我想这是或多或少类似于由“用户未知”给出的答案，只有没有递归和集合。
存储器(和处理)足迹，需要为笛卡尔的产品可以获得的手很快。天真实施，可以排的存储器，并采取了很多时间。这将是很好要知道的操作计划，以执行在这样的设置，以便提出一个执行战略。
在任何情况下，做点什么喜欢套。SetView在谷歌的集合。这是一个设得到支持的其他组，因为他们得到增加。这个想法 他们 问题是避免addAll的呼吁。这个想法 你的 问题是避免使NxMxK增加了一个集。
谷歌的收藏品可以在这里找到 和上述类 在这里，
关于使用odl.com.google.common18.collect.Sets如何 和调用Sets.cartesianProduct（）方法
不隶属于 StackOverflow
