partition of a set or all possible subgroups of a list

Question

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

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?

possible duplicate of [Split a list into two sublists in all possible ways](http://stackoverflow.com/questions/29656649/split-a-list-into-two-sublists-in-all-possible-ways) — Nir Alfasi, Apr 21 '15 at 04:18
You are missing the partition [[1,4],[2],[3]] from your expected output. Can you edit your question and add it? Thanks. I would also correct the syntax and put commas between your lists. And I would perhaps change your lists to sets to explicitly show that the order is irrelevant. Also, are you just interested in getting the Bell number? There is an easier way to do that. — tommy.carstensen, Apr 21 '15 at 15:11
Check out this post, if you just want to calculate the Bell Number: http://codereview.stackexchange.com/questions/12119/printing-nth-bell-number — tommy.carstensen, Apr 21 '15 at 15:13
Does this answer your question? [Set partitions in Python](https://stackoverflow.com/questions/19368375/set-partitions-in-python) — tommy.carstensen, Aug 07 '20 at 04:05

score 1 · Accepted Answer · edited May 23 '17 at 12:21

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))))

It prints:

[{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

partition of a set or all possible subgroups of a list

1 Answers1

Linked