一尘不染

Java迭代笛卡尔积

algorithm

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

…但是我发现它很不雅致。有人有更好的迭代解决方案吗?使用一些类似于功能的出色方法的解决方案?否则…关于如何改善它的建议?错误吗?


阅读 235

收藏
2020-07-28

共1个答案

一尘不染

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

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

编辑: 该代码现已发布。

Sets.cartesianProduct()

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

如果您想检查源,请在此处

请享用!

2020-07-28