java - 在Java中查找集合的所有分区

Question

我有以下 Python 函数来递归查找集合的所有分区:

def partitions(set_):
    if not set_:
        yield []
        return
    for i in xrange(2**len(set_)/2):
        parts = [set(), set()]
        for item in set_:
            parts[i&1].add(item)
            i >>= 1
        for b in partitions(parts[1]):
            yield [parts[0]]+b

for p in partitions(["a", "b", "c", "d"]):
    print(p)

有人可以帮我把它翻译成 Java 吗？这是我目前所拥有的:

private static List<List<List<String>>> partitions(List<String> inputSet) {
    List<List<List<String>>> res = Lists.newArrayList();
    if (inputSet.size() == 0) {
        List<List<String>> empty = Lists.newArrayList();
        res.add(empty);
        return res;
    }
    int limit = (int)(Math.pow(2, inputSet.size())/2);
    for (int i = 0; i<limit; i++) {
        List<List<String>> parts = Lists.newArrayList();
        List<String> part1 = Lists.newArrayList();
        List<String> part2 = Lists.newArrayList();
        parts.add(part1);
        parts.add(part2);
        for (String item: inputSet) {
            parts.get(i&1).add(item);
            i >>= 1;
        }
        for (List<List<String>> b: partitions(parts.get(1))) {
            List<List<String>> set = Lists.newArrayList();
            set.add(parts.get(0));
            set.addAll(b);
            res.add(set);
        }
    }
    return res;
}

当使用多个元素执行它时，我得到了一个无限递归。

可以找到与此类似的帖子(使用 Ruby)here .可以找到原始的 Python 代码 here和 here .

Answer 1

您非常接近正确答案。你说你得到了无限递归，但实际上程序在最外层循环中运行在无限循环中。

与 Python 代码的主要区别在于 i在 Python 版本中，变量总是在外循环中前进，但在您的 Java 版本中，i >>= 1内循环中的语句总是离开 i回到零。解决这个问题的简单方法是简单地为内循环和外循环使用单独的变量。

一般来说，这就是为什么尝试直接将程序从一种语言翻译成另一种语言是个坏主意的原因。几乎每个程序都有一些习语，这些习语在源语言中有意义，而在目标语言中却很奇怪或毫无意义。特别是，Python 代码的正确性依赖于对任意精度整数的隐式提升。这在 Java 中效果不佳，因此如果输入集大于 31 个元素，则下面的实现会出现整数溢出。您的示例只有 4 个元素，因此对于这种特定情况，它将产生正确的答案。

这是一个更正的 Java 版本:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Partition {
    private static List<List<List<String>>> partitions(List<String> inputSet) {
        List<List<List<String>>> res = new ArrayList<>();
        if (inputSet.isEmpty()) {
            List<List<String>> empty = new ArrayList<>();
            res.add(empty);
            return res;
        }
        // Note that this algorithm only works if inputSet.size() < 31
        // since you overflow int space beyond that. This is true even
        // if you use Math.pow and cast back to int. The original
        // Python code does not have this limitation because Python
        // will implicitly promote to a long, which in Python terms is
        // an arbitrary precision integer similar to Java's BigInteger.
        int limit = 1 << (inputSet.size() - 1);
        // Note the separate variable to avoid resetting
        // the loop variable on each iteration.
        for (int j = 0; j < limit; ++j) {
            List<List<String>> parts = new ArrayList<>();
            List<String> part1 = new ArrayList<>();
            List<String> part2 = new ArrayList<>();
            parts.add(part1);
            parts.add(part2);
            int i = j;
            for (String item : inputSet) {
                parts.get(i&1).add(item);
                i >>= 1;
            }
            for (List<List<String>> b : partitions(part2)) {
                List<List<String>> holder = new ArrayList<>();
                holder.add(part1);
                holder.addAll(b);
                res.add(holder);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        for (List<List<String>> partitions :
                 partitions(Arrays.asList("a", "b", "c", "d"))) {
            System.out.println(partitions);
        }
    }
}

这是我的 Java 版本的输出:

[[a, b, c, d]]
[[b, c, d], [a]]
[[a, c, d], [b]]
[[c, d], [a, b]]
[[c, d], [b], [a]]
[[a, b, d], [c]]
[[b, d], [a, c]]
[[b, d], [c], [a]]
[[a, d], [b, c]]
[[a, d], [c], [b]]
[[d], [a, b, c]]
[[d], [b, c], [a]]
[[d], [a, c], [b]]
[[d], [c], [a, b]]
[[d], [c], [b], [a]]