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?

This is not a duplicate of [Python: show all possible groupings of a list, given only the amount of sublists (lengths are variable)](https://stackoverflow.com/q/9088321); that question only produces a fixed number of splits, in all possible locations. — Martijn Pieters, Apr 07 '16 at 08:41
@MartijnPieters - Only one split? `>>> list(split_list([1, 2, 3, 4], 3))` -> `[[[1], [2], [3, 4]], [[1], [2, 3], [4]], [[1, 2], [3], [4]]]` — TigerhawkT3, Apr 07 '16 at 08:50
@TigerhawkT3: so you'd have to cycle and create more and more splits. It can be done far more efficiently for this usecase. — Martijn Pieters, Apr 07 '16 at 08:54
@TigerhawkT3: comment edited to use *fixed number* rather than *one*. — Martijn Pieters, Apr 07 '16 at 08:56

Martijn Pieters · Accepted Answer · 2016-04-07T08:46:56.850

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

score 1 · Answer 2 · edited May 23 '17 at 12:15

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]]

Python: breaking a list into all possible sublists

2 Answers2

Linked