Python: breaking a list into all possible sublists

Question

Lets assume I've got a list of integers:

mylist = [101, 102, 103, 104, 105, 106]

Now I need to create every possible sublist division (order preserved):

sublists = [([101], [102, 103, 104, 105, 106]),
            ([101, 102], [103, 104, 105, 106]),
            ([101, 102, 103], [104, 105, 106]),
            ...
            ([101, 102], [103, 104], [105, 106]),
            ...
            ([101], [102, 103, 104], [105], [106]),
            ...
            ([101], [102], [103], [104], [105], [106])]

Any idea? Would itertools be helpful?

Answer 1

You are creating slice points; are you slicing after the current element or not. You can generate these with booleans:

from itertools import product

def sublists(lst):
    for doslice in product([True, False], repeat=len(lst) - 1):
        slices = []
        start = 0
        for i, slicehere in enumerate(doslice, 1):
            if slicehere:
                slices.append(lst[start:i])
                start = i
        slices.append(lst[start:])
        yield slices

Demo:

>>> from pprint import pprint
>>> mylist = [101, 102, 103, 104, 105, 106]
>>> pprint(list(sublists(mylist)))
[[[101], [102], [103], [104], [105], [106]],
 [[101], [102], [103], [104], [105, 106]],
 [[101], [102], [103], [104, 105], [106]],
 [[101], [102], [103], [104, 105, 106]],
 [[101], [102], [103, 104], [105], [106]],
 [[101], [102], [103, 104], [105, 106]],
 [[101], [102], [103, 104, 105], [106]],
 [[101], [102], [103, 104, 105, 106]],
 [[101], [102, 103], [104], [105], [106]],
 [[101], [102, 103], [104], [105, 106]],
 [[101], [102, 103], [104, 105], [106]],
 [[101], [102, 103], [104, 105, 106]],
 [[101], [102, 103, 104], [105], [106]],
 [[101], [102, 103, 104], [105, 106]],
 [[101], [102, 103, 104, 105], [106]],
 [[101], [102, 103, 104, 105, 106]],
 [[101, 102], [103], [104], [105], [106]],
 [[101, 102], [103], [104], [105, 106]],
 [[101, 102], [103], [104, 105], [106]],
 [[101, 102], [103], [104, 105, 106]],
 [[101, 102], [103, 104], [105], [106]],
 [[101, 102], [103, 104], [105, 106]],
 [[101, 102], [103, 104, 105], [106]],
 [[101, 102], [103, 104, 105, 106]],
 [[101, 102, 103], [104], [105], [106]],
 [[101, 102, 103], [104], [105, 106]],
 [[101, 102, 103], [104, 105], [106]],
 [[101, 102, 103], [104, 105, 106]],
 [[101, 102, 103, 104], [105], [106]],
 [[101, 102, 103, 104], [105, 106]],
 [[101, 102, 103, 104, 105], [106]],
 [[101, 102, 103, 104, 105, 106]]]

If you want to drop the last entry (containing a list with only one list in it, in turn containing all elements), replace the last 2 lines with:

if start:
    slices.append(lst[start:])
    yield slices

Answer 2

This is an interesting question! Although Martijn has given an elegant answer, I'd still like to post mine that tackles this problem from another angle - Divide & Conquer:

def sublist_gen(ls):
    n = len(ls)
    if n == 1:
        yield [ls]
    else:
        for left in sublist_gen(ls[0:n/2]):
            for right in sublist_gen(ls[n/2:n]):
                yield left + right
                yield left[0:-1] + [left[-1] + right[0]] + right[1:]

mylist = [101, 102, 103, 104, 105, 106]
for sublist in sublist_gen(mylist):
    print(sublist)

Result:

[[101], [102], [103], [104], [105], [106]]
[[101], [102], [103, 104], [105], [106]]
[[101], [102], [103], [104, 105], [106]]
[[101], [102], [103, 104, 105], [106]]
[[101], [102], [103], [104], [105, 106]]
[[101], [102], [103, 104], [105, 106]]
[[101], [102], [103], [104, 105, 106]]
[[101], [102], [103, 104, 105, 106]]
[[101, 102], [103], [104], [105], [106]]
[[101, 102], [103, 104], [105], [106]]
[[101, 102], [103], [104, 105], [106]]
[[101, 102], [103, 104, 105], [106]]
[[101, 102], [103], [104], [105, 106]]
[[101, 102], [103, 104], [105, 106]]
[[101, 102], [103], [104, 105, 106]]
[[101, 102], [103, 104, 105, 106]]
[[101], [102, 103], [104], [105], [106]]
[[101], [102, 103, 104], [105], [106]]
[[101], [102, 103], [104, 105], [106]]
[[101], [102, 103, 104, 105], [106]]
[[101], [102, 103], [104], [105, 106]]
[[101], [102, 103, 104], [105, 106]]
[[101], [102, 103], [104, 105, 106]]
[[101], [102, 103, 104, 105, 106]]
[[101, 102, 103], [104], [105], [106]]
[[101, 102, 103, 104], [105], [106]]
[[101, 102, 103], [104, 105], [106]]
[[101, 102, 103, 104, 105], [106]]
[[101, 102, 103], [104], [105, 106]]
[[101, 102, 103, 104], [105, 106]]
[[101, 102, 103], [104, 105, 106]]
[[101, 102, 103, 104, 105, 106]]