Estou fazendo algumas experiências de segmentação de palavras como as seguintes.

lst é uma sequência de caracteres eoutput são todas as palavras possíveis.

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

Eu verifiqueicombinations epermutations noitertools biblioteca,
e também tenteicombinatória.
No entanto, parece que estou olhando para o lado errado, porque isso não é pura permutação e combinações ...

Parece que posso conseguir isso usando muitos loops, mas a eficiência pode ser baixa.

EDITAR

A ordem das palavras é importante, portanto, combinações como['ba', 'dc'] ou['cd', 'ab'] não são válidos.

O pedido deve sempre serda esquerda para a direita.

EDITAR

A solução do @ Stuart não funciona no Python 2.7.6

EDITAR

A solução do @ Stuart funciona no Python 2.7.6, veja os comentários abaixo.