Estoy haciendo algunos experimentos de segmentación de palabras como los siguientes.

lst es una secuencia de caracteres, youtput Es todas las palabras posibles.

lst = ['a', 'b', 'c', 'd']

def foo(lst):
    ...
    return output

output = [['a', 'b', 'c', 'd'],
          ['ab', 'c', 'd'],
          ['a', 'bc', 'd'],
          ['a', 'b', 'cd'],
          ['ab', 'cd'],
          ['abc', 'd'],
          ['a', 'bcd'],
          ['abcd']]

He comprobadocombinations ypermutations enitertools biblioteca,
y también probécombinatoria.
Sin embargo, parece que estoy mirando el lado equivocado porque esto no es pura permutación y combinaciones ...

Parece que puedo lograr esto usando muchos bucles, pero la eficiencia puede ser baja.

EDITAR

El orden de las palabras es importante, así que combinaciones como['ba', 'dc'] o['cd', 'ab'] No son válidos.

El orden siempre debe serde izquierda a derecha.

EDITAR

La solución de @ Stuart no funciona en Python 2.7.6

EDITAR

La solución de @ Stuart funciona en Python 2.7.6, vea los comentarios a continuación.