All supplementary subsets of a list in python

Question

I am not sure if 'supplementary' is the right word, but I will explain my problem with an example. Let's say our list is:

[1,2,3,4]

What I am trying to find is:

[1], [2], [3], [4]
[1,2], [3], [4]
[1,3], [2], [4]
...
[1,2], [3,4]
[1,3], [2,4]
...
[1,2,3], [4]
[1,2,4], [3]
...
[1,2,3,4]

In other words, I try to get all lists such that they together have all elements of the initial list.

Thanks!

this is obviously not a duplicate with that question. please pay more attention.. @unutbu — lincinthesink, Oct 04 '17 at 01:15
Try to find code samples for `power set`. A powerset is the set of all subsets. https://en.wikipedia.org/wiki/Power_set — Edward Minnix, Oct 04 '17 at 01:31
@Adam Smith, you use combinations to enumerate the cases then use that to reference back the original objects. — Spinor8, Oct 04 '17 at 01:34
Also, rudeness is uncalled for. Your [first comment](https://stackoverflow.com/questions/46555589/all-supplementary-subsets-of-a-list-in-python?noredirect=1#comment80065301_46555589) is not very polite. — cs95, Oct 04 '17 at 01:36
@COLDSPEED. I am sorry if you found it rude. Meanwhile, you closed the question again, but I have to say that it is not duplicate with that question either.. — lincinthesink, Oct 04 '17 at 01:45

unutbu · Accepted Answer · 2017-10-05T02:28:30.637

You could use Raymond Hettinger's partition recipe to find all partitions. I've modified it slightly to work with Python3. I also added partition_permutations to find the partitions of all permutations of the input, x.

import pprint
import itertools as IT

def partition(iterable, chain=IT.chain, map=map):
    """
    http://code.activestate.com/recipes/576795/ (Raymond Hettinger)
    >>> list(partition('abcd'))
    [['abcd'],
     ['a', 'bcd'],
     ['ab', 'cd'],
     ['abc', 'd'],
     ['a', 'b', 'cd'],
     ['a', 'bc', 'd'],
     ['ab', 'c', 'd'],
     ['a', 'b', 'c', 'd']]
    """
    s = iterable if hasattr(iterable, '__getitem__') else tuple(iterable)
    n = len(s)
    first, middle, last = [0], range(1, n), [n]
    getitem = s.__getitem__
    return [list(map(getitem, map(slice, chain(first, div), chain(div, last))))
            for i in range(n) for div in IT.combinations(middle, i)]

def partition_permutations(iterable, ordered_partitions=False):
    result = set()
    for perm in IT.permutations(iterable):
        for item in partition(perm):
            if ordered_partitions:
                result.add(tuple(item))
            else:
                result.add(tuple(sorted(item)))
    result = [list(map(list, item)) for item in result]
    result = sorted(result)
    return result


x = [1,2,3,4]
result = partition_permutations(x, ordered_partitions=True)
pprint.pprint(result)
print(len(result))

yields 73 items:

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

Note that partition_permutations treats the items inside each partition as unordered. That is, for example, [[1,4], [2,3]] and [[2,3], [1,4]] are treated as the same partition. If that is not what you want, then change

result = partition_permutations(x)

to

result = partition_permutations(x, ordered_partitions=True)

Thanks. It is really close to what I am looking for, but it does not return some lists. For example: [[1,4], [2,3]] or [[1,4], [2], [3]]. — lincinthesink, Oct 04 '17 at 13:22

All supplementary subsets of a list in python

1 Answers1