迭代笛卡尔积在Java中 [英] Iterative Cartesian Product in Java

问题描述

我要计算的任意数目的笛卡尔积的非空套​​在Java中。

I want to compute the cartesian product of an arbitrary number of nonempty sets in Java.

我已经写了反复code ...

I've wrote that iterative code...

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 I found it rather inelegant. Someone has a better, still iterative solution? A solution that uses some wonderful functional-like approach? Otherwise... suggestion about how to improve it? Errors?

感谢：）

推荐答案

我已经写了，不需要你填写了一个大集合的内存解决方案。不幸的是，所需的code是数百线长。您可能要等到它出现在番石榴项目上（http：//guava-libraries.google$c$c.com），我希望会在今年年底。抱歉。 ：（

I've written a solution that doesn't require you to fill up a large collection in memory. Unfortunately, the code required is hundreds of lines long. You may have to wait until it appears in the Guava project (http://guava-libraries.googlecode.com), which I hope will be by the end of the year. Sorry. :(

请注意，你可能不会需要这样的工具，如果套你是笛卡尔产区的数量是在编译时已知的固定数量 - 你可以只使用了一些嵌套的for循环

Note that you may not need such a utility if the number of sets you're cartesian-producting is a fixed number known at compile time -- you could just use that number of nested for loops.

编辑：的code，现予以公布

the code is released now.

<一个href="http://guava-libraries.google$c$c.com/svn/trunk/javadoc/com/google/common/collect/Sets.html#cartesianProduct%28java.util.Set...%29"><$c$c>Sets.cartesianProduct()

我想你会很高兴的。当你问他们这只会造成个人名单;不填满记忆与他们的所有MxNxPxQ。

I think you'll be very happy with it. It only creates the individual lists as you ask for them; doesn't fill up memory with all MxNxPxQ of them.

如果你想查看源代码，这是<一href="http://$c$c.google.com/p/guava-libraries/source/browse/trunk/src/com/google/common/collect/Sets.java">here在行727 。

If you want to inspect the source, it's here at line 727.

享受！

这篇关于迭代笛卡尔积在Java中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！