Set partitions in Python

Solution 1:

Since this nice question has been brought back to life, here's a fresh answer.

The problem is solved recursively: If you already have a partition of n-1 elements, how do you use it to partition n elements? Either place the n'th element in one of the existing subsets, or add it as a new, singleton subset. That's all it takes; no itertools, no sets, no repeated outputs, and a total of just n calls to partition():

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[:1]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [first + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ first ] + smaller


something = list(range(1,5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))

Output:

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]

Solution 2:

Unlike my comments suggested, I was unable to quickly find an itertools based relatively fast solution! Edit: this is no longer quite true, I have a fairly short (but slow and unreadable) solution using itertools largely, see the end of the answer. This is what I got instead:

The idea is that we find all the combinations of integers that add up to the length of the list, and then get lists with slices of that length.

E.g. for a list of length 3, the combinations, or partitions, are (3), (2, 1), (1, 2) and (1, 1, 1). So we return the first 3 items of the list; the first 2 and then the next 1; the first 1 then the next 2 and the first 1, then the next 1, then the next 1.

I got code for integer partioning from here. However, partition functions don't return all permutations of the partitions (i.e. for 3 it would just return (3), (2, 1) and (1, 1, 1). So we need to call itertools.permutations on each of the partitions. We then need to remove duplicates - just as permutations([1, 2, 3]) is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]; permutations([1, 1, 1]) is [[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]]. An easy way of removing duplicates is by turning each list of tuples into a set.

Then all that remains is getting slices of the list the for the lengths in the tuple. E.g. f([1, 2, 3], [0, 0, 1, 2, 1, 0]) goes to [[0], [0, 1], [2, 1, 0]].

My definition of that is this:

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

Now we just combine everything:

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

>>> for i in subgrups(my_list):
        print(i)

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

Also, you need to do import itertools and from copy import deepcopy at the top of the program as well.

Edit: your given output is unclear. I presumed you wanted the function that I have given you, but your output also contains [[1,3],[2]], where the elements in the output are in a different order, unlike the rest of your suggested output (I have taken the liberty of presuming you actually want [[1, 2], [3]] not [[1, 2], 3]).

That is to say, I presume what you meant to give as output was this:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]

If in actual fact it was this:

[[1], [2], [3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[1, 2, 3]]
[[1], [3], [2]]
[[1], [3, 2]]
[[1, 3], [2]]
[[1, 3, 2]]
[[2], [1], [3]]
[[2], [1, 3]]
[[2, 1], [3]]
[[2, 1, 3]]
[[2], [3], [1]]
[[2], [3, 1]]
[[2, 3], [1]]
[[2, 3, 1]]
[[3], [1], [2]]
[[3], [1, 2]]
[[3, 1], [2]]
[[3, 1, 2]]
[[3], [2], [1]]
[[3], [2, 1]]
[[3, 2], [1]]
[[3, 2, 1]]

Then you simply need to call subgrups for each 3-length permutation of the original list, e.g. for each permutation in itertools.permutations(my_list, len(my_list)).

Edit: Now to hold up to my promise of a short itertools based solution. Warning - it may be both unreadable and slow.

First we replace slice_by_lengths with this:

def sbl(lengths, the_list):
    for index, length in enumerate(lengths):
        total_so_far = sum(lengths[:index])
        yield the_list[total_so_far:total_so_far+length]

Then from this answer we get our integer partitioning function:

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

This function actually gets all permutations of the integer partitions for us, so we don't need

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

anymore. However, it is much slower than what we had before, as it is recursive (and we are implementing it in Python).

Then we just put it together:

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

Or less readable, but without the function definitions:

def subgrups(my_list):
    for each_tuple in (lambda p, f=lambda n, g:
                          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
                              f(p, f))(len(my_list)):
        yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))

which is a function definition and two lines, so fairly close to what I originally stated (although much less readable and much slower)!

(Functions called subgrups because the question originally asked to find "all subgrups")