迭代计算任意数量集合的笛卡尔积 [英] Iteratively compute the Cartesian product of an arbitrary number of sets

问题描述

我想用 Java 计算任意数量的非空集的笛卡尔积.

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

我已经编写了迭代代码...

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?

推荐答案

我编写了一个不需要您在内存中填满大量集合的解决方案.不幸的是，所需的代码长达数百行.你可能要等到它出现在 Guava 项目中 (https://github.com/google/guava)，我希望能在今年年底完成.对不起.:(

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 (https://github.com/google/guava), 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.

代码现已发布.

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.

如果你想检查源代码，它是 这里.

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

享受吧！

这篇关于迭代计算任意数量集合的笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！