Найти все возможные упорядоченные группы в списке

Question

Учитывая упорядоченный список целых чисел:

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

Я в основном ищет способ, чтобы генерировать все перестановки списка, где поддерживается порядок. Я могу создать все подсписки, где Есть только 2 подсписки в общей сложности, используя этот код:

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

Однако это фрагменты кода только разбивает исходный список на два и генерирует все возможные подсписки, где Есть только два подсписки. Как я могу сгенерировать все возможные подсписки, которые могут быть созданы из исходного списка, где поддерживается порядок?

Answer 1

Как насчет:

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 

Результат:

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