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库检查combinations和permutations，
也试过combinatorics。
但是，似乎我看着错误的一面，因为这不是纯粹的置换和组合...

看来我可以通过使用大量循环来实现这一点，但效率可能很低。所以像['ba', 'dc']或['cd', 'ab']组合是无效的

编辑

词序是很重要的。

从左至右的顺序应始终为。

编辑

@斯图尔特的解决方案并不在Python 2.7.6工作

编辑

@斯图尔特的解决方案确实在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 

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

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

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递归限制的程度。与其他一些答案类似，您也可以使用combinations从itertools开始处理每个可能的组合点。

这些似乎都按预期在Python 2.7（see here）和Python 3.2（here）工作。正如@twasbrillig所说，确保你缩进如图所示。