Java中的迭代笛卡尔积

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (82)

我想计算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;
}

...但我发现它相当不雅。有人有更好的,仍然迭代的解决方案?一种解决方案使用了一些非常类似功能的方法?否则...有关如何改进它的建议?错误?

提问于
用户回答回答于

我写了一个解决方案,不需要你在内存中填充一个大集合。不幸的是,所需的代码长达数百行。您可能需要等到它出现在Guava项目(http://guava-libraries.googlecode.com)中,我希望在年底之前。抱歉。:(

请注意,如果您的笛卡尔积的数量是编译时已知的固定数量,那么您可能不需要这样的实用程序 - 您可以使用该嵌套for循环的数量。

代码现在发布。

Sets.cartesianProduct()

我想你会对此感到满意。它只会根据您的要求创建单个列表; 不会用它们中的所有MxNxPxQ填充内存。

用户回答回答于

以下答案使用迭代而不是递归。它使用Tuple我以前答案中的同一个类。

这是一个单独的答案,因为恕我直言,都是有效的,不同的方法。

这是new main class:

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

扫码关注云+社区