Find all possible ordered groups in the list.

Question

For an ordered list of integers:

[1,3,7,8,9]

How can I find all the sublists that can be created from the source list, where the order is maintained? Using the above example, I am looking for a way to programmatically generate these sequences:

[[1],[3,7,8,9]]
[[1, 3],[7,8,9]]
[[1, 3, 7],[8,9]]
[[1, 3, 7, 8],[9]]
[[1, 3, 7, 8, 9]]
[[1, 3, 7], [8, 9]]
[[1], [3, 7], [8], [9]]
[[1], [3], [7, 8], [9]]
[[1], [3], [7], [8, 9]]
...

I'm basically looking for a way to create all permutations of a list in which order is maintained. I can generate all sublists in which there are only 2 subscriptions using this code:

def partition(arr, idx):
    return [arr[:idx], arr[idx:]]

l = [1,3,7,8,9]
for idx in range(1, len(l)):
    groups = partition(l, idx)
    print(groups)

[[1], [3, 7, 8, 9]]
[[1, 3], [7, 8, 9]]
[[1, 3, 7], [8, 9]]
[[1, 3, 7, 8], [9]]

However, this piece of code only divides the source list in half and generates all possible signatures that have only two sublists. How can I generate all possible sublists that can be created from the original list, where the order is maintained?

Answer 1

What about:

import itertools

def subsets(seq):
    for mask in itertools.product([False, True], repeat=len(seq)):
        yield [item for x, item in zip(mask, seq) if x]

def ordered_groups(seq):
    for indices in subsets(range(1, len(seq))):
        indices = [0] + indices + [len(seq)]
        yield [seq[a:b] for a,b in zip(indices, indices[1:])]

for group in ordered_groups([1,3,7,8,9]):
    print group

Result:

[[1, 3, 7, 8, 9]]
[[1, 3, 7, 8], [9]]
[[1, 3, 7], [8, 9]]
[[1, 3, 7], [8], [9]]
[[1, 3], [7, 8, 9]]
[[1, 3], [7, 8], [9]]
[[1, 3], [7], [8, 9]]
[[1, 3], [7], [8], [9]]
[[1], [3, 7, 8, 9]]
[[1], [3, 7, 8], [9]]
[[1], [3, 7], [8, 9]]
[[1], [3, 7], [8], [9]]
[[1], [3], [7, 8, 9]]
[[1], [3], [7, 8], [9]]
[[1], [3], [7], [8, 9]]
[[1], [3], [7], [8], [9]]