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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在Java中查找集合的所有分区，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3484字，纯文字阅读大概需要5分钟。

内容图文

我有以下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找到.

解决方法:

你非常接近正确的答案.你说你正在获得无限递归,但实际上程序在最外层循环中以无限循环运行.

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

内容总结

以上是互联网集市为您收集整理的在Java中查找集合的所有分区全部内容，希望文章能够帮你解决在Java中查找集合的所有分区所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端