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

我已经检查了itertools库中的排列和组合，还尝试了combinatorics。但是，似乎我看错了，因为这不是纯排列和组合... 似乎我可以通过使用许多循环来实现这一点，但效率可能很低。

编辑

单词顺序很重要，因此像['ba'，'dc']或['cd'，'ab']这样的组合是无效的。

顺序应始终从左到右。

编辑

@Stuart的解决方案在Python 2.7.6中无法工作。

编辑

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

- amigcamel

---

请查看我的Python 2.7.3版本的代码演示链接，以及Python 3.2.3版本的代码演示链接。 - Stuart

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

- Sriram

---

我选择这个答案是因为它花费的时间最少，但其他人的解决方案也很棒！ - amigcamel

Answer 2

有8个选项，每个选项都镜像二进制数0到7：

000
001
010
011
100
101
110
111

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

>>> lst = ['a', 'b', 'c', 'd']
... output = []
... formatstr = "{{:0{}.0f}}".format(len(lst)-1)
... for i in range(2**(len(lst)-1)):
...     output.append([])
...     s = "{:b}".format(i)
...     s = str(formatstr.format(float(s)))
...     lstcopy = lst[:]
...     for j, c in enumerate(s):
...         if c == "1":
...             lstcopy[j+1] = lstcopy[j] + lstcopy[j+1]
...         else:
...             output[-1].append(lstcopy[j])
...     output[-1].append(lstcopy[-1])
... output
[['a', 'b', 'c', 'd'],
 ['a', 'b', 'cd'],
 ['a', 'bc', 'd'],
 ['a', 'bcd'],
 ['ab', 'c', 'd'],
 ['ab', 'cd'],
 ['abc', 'd'],
 ['abcd']]
>>> 

- twasbrillig

---

你的代码在 lst = ['a','b','c','d','e'] 上不起作用。 - Marcin Fabrykowski

谢谢！我已经修复了代码，现在可以处理更多字母的情况。即使我没有得到认可，这也是一次有趣的练习 :) - twasbrillig

哈哈！我已经给你点赞了。我们都有相同的解决方案。你更快！ :-) - Sriram

谢谢！是的，我们以同样的方式看待这个问题，你的代码很好地利用了itertools库，我会去学习一下。 - twasbrillig

Answer 3

#!/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)

输出：

zsh 2419 % ./words.py  
['abcd']
['a', 'bcd']
['ab', 'cd']
['abc', 'd']
['a', 'b', 'cd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

- Marcin Fabrykowski

---

我无法给你点赞。我在你的回答下面写了原因。 你的代码比我的短，这很好，但是在我的电脑上你的代码运行不太好 :( - Marcin Fabrykowski

那实际上是 Stuart 的回答，不是我的，但 Sririam 给了我点赞，所以一切都好。 - twasbrillig

Answer 4

您可以使用递归生成器：

def split_combinations(L):
    for split in range(1, len(L)):
        for combination in split_combinations(L[split:]):
            yield [L[:split]] + combination
    yield [L]

print (list(split_combinations('abcd')))

编辑。我不确定这种方法在处理长字符串时是否能很好地扩展，并且它何时会达到Python的递归限制。与其他答案类似，您还可以使用itertools中的combinations来处理每个可能的分割点组合。

def split_string(s, t):
    return [s[start:finish] for start, finish in zip((None, ) + t, t + (None, ))]

def split_combinations(s):
    for i in range(len(s)):
        for split_points in combinations(range(1, len(s)), i):
            yield split_string(s, split_points)

在Python 2.7（在这里看到）和Python 3.2（在这里）中，这两个似乎都可以正常工作。如@twasbrillig所说，请确保缩进与示例相同。

- Stuart

---

我在输出中没有看到 ['abc' 'd']。 - Marcin Fabrykowski

>>> def split_combinations(L): ... for split in range(1, len(L)): ... for combination in split_combinations(L[split:]): ... yield [L[:split]] + combination ... yield [L] ... print (list(split_combinations('abcd'))) [['a', 'b', 'c', 'd'], ['a', 'b', 'cd'], ['a', 'bc', 'd'], ['a', 'bcd'], ['ab', 'c', 'd'], ['ab', 'cd'], ['abc', 'd'], ['abcd']] - twasbrillig

Python 3.4.0（默认，2014年4月11日，13:05:11） - Marcin Fabrykowski

你可以在新的SO问题中询问为什么存在差异。 - twasbrillig

找到了差异。如果将 yield [L] 缩进两次而不是一次，我会得到错误的结果。确保它只缩进一次，你应该能得到正确的答案。 - twasbrillig