集合划分或列表的所有可能的分组 [英] partition of a set or all possible subgroups of a list

问题描述

让我们说我有一个列表[1,2,3,4]我想要制作这一套涵盖所有成员一次，结果应该有15列出其顺序并不重要，相反的T所有子集提供所有可能的亚组：

Let's say I have a list of [1,2,3,4] I want to produce all subsets of this set which covers all members once, the result should has 15 lists which the order isn't important, instead t provides all possible subgroups:

>>>>[[1,2,3,4]]
[[1][2][3][4]]
[[1,2],[3][4]]
[[1,2],[3,4]]
[[1][2],[3,4]]
[[1,3],[2][4]]
[[1,3],[2,4]]
[[1][3],[2,4]]
[[1],[2,3][4]]
[[1,4],[2,3]]
[[1][2,3,4]]
[[2][1,3,4]]
[[3][1,2,4]]
[[4][1,2,3]]

这是一组划分问题或这是讨论的的分区= http://stackoverflow.com/questions/19368375/set-partitions-in-python\">here ，但反应让我感到困惑，因为它只是表明回顾排列，但我不知道怎么办！和另一个响应也不包括[的1,3 ]
同时，我应该解决这个问题的高数和结果应提供贝尔数
对不起，我很新的蟒蛇，成为困惑。任何人都可以将T清楚我吗？

This is a set partitioning problem or partitions of a set which is discussed here, but the response made me confused as it just suggests recalling permutations, but I don't know how! and another response also doesn't include [1,3] Meanwhile I should solve this problem for high numbers and the result should provide Bell Number Sorry I'm quite new to python and became confused. Could anyone make t clear for me?

推荐答案

而不是做所有的排列和删除重复的，这是我最初的想法，那么你可以使用这个递归函数，我发现<一的href=\"http://stackoverflow.com/questions/2037327/translating-function-for-finding-all-partitions-of-a-set-from-python-to-ruby\">here和这里

Instead of doing all permutations and remove the duplicates, which was my initial thought, then you can use this recursive function, which I found here and here:

def partitions(set_):
    if not set_:
        yield []
        return
    for i in range(int(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

l = [1, 2, 3, 4]
for p in reversed(sorted(partitions(l))):
    print(p)
print('The Bell number is', len(list(partitions(l))))

它打印：

[{1, 2, 3, 4}]
[{1, 2, 4}, {3}]
[{1, 4}, {2, 3}]
[{1, 4}, {3}, {2}]
[{2, 4}, {1, 3}]
[{2, 4}, {3}, {1}]
[{1, 3, 4}, {2}]
[{2, 3, 4}, {1}]
[{3, 4}, {1, 2}]
[{3, 4}, {2}, {1}]
[{4}, {1, 2, 3}]
[{4}, {1, 3}, {2}]
[{4}, {2, 3}, {1}]
[{4}, {3}, {1, 2}]
[{4}, {3}, {2}, {1}]
The Bell number is 15

这篇关于集合划分或列表的所有可能的分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！