I'm doing some word segmentation experiments like the followings.
lst is a sequence of characters, and
output is all the possible words.
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']]
and also tried combinatorics.
However, it seems that I'm looking at the wrong side because this is not pure permutation and combinations...
It seems that I can achieve this by using lots of loops, but the efficiency might be low.
The word order is important so combinations like
['ba', 'dc'] or
['cd', 'ab'] are not valid.
The order should always be from left to right.
@Stuart's solution doesn't work in Python 2.7.6
@Stuart's solution does work in Python 2.7.6, see the comments below.