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

一尘不染

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

algorithm

我具有以下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）类似的帖子。原始Python代码可和此处找到。

阅读 230

2020-07-28

共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]]

2020-07-28