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和{}在itertools库中，
也尝试了combinatorics。
然而，似乎我看错了方向，因为这不是纯粹的排列组合。。。在

似乎我可以通过使用很多循环来实现这一点，但是效率可能很低。在

编辑

词序很重要，所以像['ba', 'dc']或{}这样的组合是无效的。在

顺序应该总是从左到右。

编辑

@Stuart的解决方案在python2.7.6中不起作用

编辑

@Stuart的解决方案在python2.7.6中确实有效，请参见下面的注释。在

Answer 1

#!/usr/bin/env python
from itertools import combinations
a = ['a', 'b', 'c', 'd']
a = "".join(a)
cuts = []
for i in range(0,len(a)):
    cuts.extend(combinations(range(1,len(a)),i))
for i in cuts:
    last = 0
    output = []
    for j in i:
        output.append(a[last:j])
        last = j
    output.append(a[last:])
    print(output)

输出：

^{pr2}$

Answer 2

有8个选项，每个选项都对应二进制数字0到7：

000
001
010
011
100
101
110
111

每个0和1表示索引处的2个字母是否“粘”在一起。0代表否，1代表是。在

^{pr2}$

Answer 3

itertools.product应该能帮到你。在

想法是这个：- 考虑A1，A2，…，a被板隔开。将有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