迭代计算任意数量的集合的笛卡尔乘积
迭代计算任意数量的集合的笛卡尔乘积
提问于 2009-11-12 10:56:16
我想在Java语言中计算任意数量的非空集的笛卡尔乘积。
我已经写好了迭代代码...
public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) {
List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size());
List<T> elements = new ArrayList<T>(list.size());
List<Set<T>> toRet = new ArrayList<Set<T>>();
for (int i = 0; i < list.size(); i++) {
iterators.add(list.get(i).iterator());
elements.add(iterators.get(i).next());
}
for (int j = 1; j >= 0;) {
toRet.add(Sets.newHashSet(elements));
for (j = iterators.size()-1; j >= 0 && !iterators.get(j).hasNext(); j--) {
iterators.set(j, list.get(j).iterator());
elements.set(j, iterators.get(j).next());
}
elements.set(Math.abs(j), iterators.get(Math.abs(j)).next());
}
return toRet;
}...but我发现它相当不雅。有人有更好的，仍然迭代的解决方案吗？一个使用一些奇妙的类似函数的方法的解决方案？否则..。关于如何改进它的建议？错误？
回答 9
Stack Overflow用户
回答已采纳
发布于 2009-11-12 23:29:16
我已经写了一个不需要你在内存中填满一个大集合的解决方案。不幸的是，所需的代码有数百行之多。您可能需要等到它出现在芭乐项目(https://github.com/google/guava)中，我希望它能在今年年底出现。抱歉的。:(
请注意，如果笛卡尔生成的集合的数量是编译时已知的固定数量，那么您可能不需要这样的实用程序--您可以只使用该数量的嵌套for循环。
EDIT:代码现已发布。
我想你会很高兴的。它只在你请求的时候创建单独的列表；不会用它们的所有MxNxPxQ来填满内存。
如果你想检查源代码，那就是here。
享受吧！
Stack Overflow用户
发布于 2016-05-28 03:14:43
使用Google Guava 19和Java 8非常简单：
假设您有要关联的所有数组的列表...
public static void main(String[] args) {
List<String[]> elements = Arrays.asList(
new String[]{"John", "Mary"},
new String[]{"Eats", "Works", "Plays"},
new String[]{"Food", "Computer", "Guitar"}
);
// Create a list of immutableLists of strings
List<ImmutableList<String>> immutableElements = makeListofImmutable(elements);
// Use Guava's Lists.cartesianProduct, since Guava 19
List<List<String>> cartesianProduct = Lists.cartesianProduct(immutableElements);
System.out.println(cartesianProduct);
}制作不可变列表列表的方法如下：
/**
* @param values the list of all profiles provided by the client in matrix.json
* @return the list of ImmutableList to compute the Cartesian product of values
*/
private static List<ImmutableList<String>> makeListofImmutable(List<String[]> values) {
List<ImmutableList<String>> converted = new LinkedList<>();
values.forEach(array -> {
converted.add(ImmutableList.copyOf(array));
});
return converted;
}输出如下：
[
[John, Eats, Food], [John, Eats, Computer], [John, Eats, Guitar],
[John, Works, Food], [John, Works, Computer], [John, Works, Guitar],
[John, Plays, Food], [John, Plays, Computer], [John, Plays, Guitar],
[Mary, Eats, Food], [Mary, Eats, Computer], [Mary, Eats, Guitar],
[Mary, Works, Food], [Mary, Works, Computer], [Mary, Works, Guitar],
[Mary, Plays, Food], [Mary, Plays, Computer], [Mary, Plays, Guitar]
]Stack Overflow用户
发布于 2009-11-12 12:44:47
下面的答案使用迭代，而不是递归。它使用与我之前的答案相同的Tuple类。
这是一个单独的答案，因为我认为两者都是有效的，不同的方法。
下面是新的主类：
public class Example {
public static <T> List<Tuple<T>> cartesianProduct(List<Set<T>> sets) {
List<Tuple<T>> tuples = new ArrayList<Tuple<T>>();
for (Set<T> set : sets) {
if (tuples.isEmpty()) {
for (T t : set) {
Tuple<T> tuple = new Tuple<T>();
tuple.add(t);
tuples.add(tuple);
}
} else {
List<Tuple<T>> newTuples = new ArrayList<Tuple<T>>();
for (Tuple<T> subTuple : tuples) {
for (T t : set) {
Tuple<T> tuple = new Tuple<T>();
tuple.addAll(subTuple);
tuple.add(t);
newTuples.add(tuple);
}
}
tuples = newTuples;
}
}
return tuples;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1719594
复制相关文章
相似问题