Python：查找所有可能的带有字符序列的单词组合（分词）

问题内容：

我正在做一些如下的分词实验。

lst是一个字符序列，并且output是所有可能的单词。

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

我已经检查combinations并permutations进入itertools图书馆，
还尝试了combinatorics。
但是，似乎我看错了一边，因为这不是纯粹的排列和组合…

看来我可以通过使用很多循环来实现，但是效率可能很低。

编辑

单词顺序很重要，因此类似['ba', 'dc']或['cd', 'ab']无效的组合。

顺序应该始终是 从左到右。

编辑

@Stuart的解决方案在Python 2.7.6中不起作用

编辑

@Stuart的解决方案在Python 2.7.6中有效，请参见下面的注释。

问题答案：

itertools.product 确实应该能够为您提供帮助。

这个想法是这样的：-考虑A1，A2，…，AN由平板分开。将有N-1个平板。如果有平板，则存在分段。如果没有平板，则存在联接。因此，对于给定的长度为N的序列，您应具有2
^（N-1）个这样的组合。

就像下面

import itertools
lst = ['a', 'b', 'c', 'd']
combinatorics = itertools.product([True, False], repeat=len(lst) - 1)

solution = []
for combination in combinatorics:
    i = 0
    one_such_combination = [lst[i]]
    for slab in combination:
        i += 1
        if not slab: # there is a join
            one_such_combination[-1] += lst[i]
        else:
            one_such_combination += [lst[i]]
    solution.append(one_such_combination)

print solution

Python：查找所有可能的带有字符序列的单词组合（分词）

微信关注