All Ways Of Partitioning A List Into Two Non-empty Lists

[0.0, 1.0, 2.0, 3.0, 4.0] I have 5 numbers and two groups, left and right. Each number has two choices - it can go left or right. I need a list that contains all partitioning of th

Solution 1:

The stuff is there in itertools, maybe you just weren't looking in the right places.

Here is teh codez:

from collections import OrderedDict
from itertools import chain, combinations

def partition(L):
    n = len(L)//2 + 1
    xs = chain(*[combinations(L, i) for i in range(1, n)])
    pairs = (tuple(sorted([x, tuple(set(L) - set(x))])) for x in xs)
    return OrderedDict.fromkeys(pairs).keys()

Output:

>>> for pair in partition([1,2,3,4]):
...     left, right = map(list, sorted(pair, key=len))
...     print left, right
...
[1] [2, 3, 4]
[2] [1, 3, 4]
[3] [1, 2, 4]
[4] [1, 2, 3]
[1, 2] [3, 4]
[1, 3] [2, 4]
[1, 4] [2, 3]