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所說，確保你縮進如圖所示。