Python:用一个字符序列找出所有可能的单词组合(分词)

Question

我正在做一些分词实验，如下所示。

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 中确实有效，请参阅下面的评论。

Answer 1

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