Set partitions in Python

Question

I have an array of [1,2,3]

I want to make all the possible combinations using all elements of the array:

Result:

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

Answer 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[0]
    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]]

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

Answer 3

Consider more_itertools.set_partitions.

Given

import more_itertools as mit


lst = [1, 2, 3]

Code

Flatten a range of k set partitions:

[part for k in range(1, len(lst) + 1) for part in mit.set_partitions(lst, k)]

Output

 [((1, 2, 3),),
  ((1,), (2, 3)),
  ((2,), (1, 3)),
  ((3,), (1, 2)),
  ((1,), (2,), (3,))]

more_itertools is a third-party package. Install via > pip install more_itertools.

Answer 4

In case someone wants to have it in JS. This indeed took me some time to implement. I was struggled with "Value & Reference" with JS.

Algorithm is the same as @alexis explained above.

Function deepCopy is clone an array, instead of copy to an array.

function deepCopy(val){
    return JSON.parse(JSON.stringify(val));
}

function partitions(arr) {
    var results = [];

    if (arr.length == 0) {
        results.push([[]]);
        return results;
    }

    if (arr.length == 1) {
        results.push(new Array(arr));
        return results;//[[[1]]]
    }

    var last = arr[arr.length - 1];
    var sub = partitions(arr.slice(0, arr.length - 1));//remove the last item

    //partitions(2) => [ [ [ 's1', 's2' ] ], [ [ 's1' ], [ 's2' ] ] ]
    //val => [ [ 's1', 's2' ] ] or [ [ 's1' ], [ 's2' ] ]
    //set => [ 's1', 's2' ] or [ 's1' ], [ 's2' ]
    sub.map((partition) => {
        //val => each partition
        //1) insert the "last" into each set, together with the rest of sets in the same partition makes a new partition
        partition.map((set) => {
            //set=>each set of one particular partition
            set.push(last);
            results.push(deepCopy(partition));
            set.pop();
        });
        //2), insert the "last" as a singlton set into the partition, make it a new partition
        partition.push([last]);
        results.push(deepCopy(partition));
        partition.pop();
    });

    return results;
}

var arr = ["s1", "s2", "s3"];
const results = partitions(arr);
console.log(results);

Outputs:

[
  [ [ 's1', 's2', 's3' ] ],
  [ [ 's1', 's2' ], [ 's3' ] ],
  [ [ 's1', 's3' ], [ 's2' ] ],
  [ [ 's1' ], [ 's2', 's3' ] ],
  [ [ 's1' ], [ 's2' ], [ 's3' ] ]
]

Answer 5

I converted alexis' answer to use loops instead of recursion. The code isn't as easy to understand but should now also work with very large sets:

def partition(collection):
    collection_except_last = reversed(collection[:-1])
    only_last = list(collection[-1:])

    # start with the partition for a 1-element collection and then add elements
    partitions = [[only_last]]
    for element in collection_except_last:
        refined_partitions = []
        for partition_ in partitions:
            # insert `element` in each of the subpartition's subsets
            for n, subset in enumerate(partition_):
                refined = partition_[:n] + [[element] + subset] + partition_[n + 1 :]
                refined_partitions.append(refined)
            # put `element` in its own subset
            refined_partitions.append([[element]] + partition_)
        partitions = refined_partitions
    return partitions