創建特定尺寸的可能組合

Question

該字符串/列表例如是'foobar的'。我需要在組數爲n的所有可能組合中將其分解，例如， 3.

這會給我例如

['foo', 'ba', 'r'] 
['f', 'ooba', 'r'] 
['fo', 'oo', 'bar'] 
['f', 'o', 'obar'] 

等

什麼是創造一切可能的組合最好的算法？

Answer 1

聽起來像是itertools工作：

from itertools import combinations 

def compositions(s,k): 
    n = len(s) 
    for c in combinations(range(1,n),k-1): 
     yield [s[i:j] for i,j in zip((0,)+c,c+(n,))] 

它的工作方式是，combinations部分產量元組其中包括可能的切點。例如（與s = "foobar"和k = 3）(2,4)是元組之一。在這些索引處打破應該產生對應於[s[0:2],s[2,4],s[4,6]]的["fo","ob","ar"]，在這種情況下的表達式zip((0,)+c,c+(n,))與zip((0,2,4),(2,4,6))相同，因此對它進行迭代具有遍歷連續切片的連續索引對的效果。

例如，

>>> for c in compositions("foobar",3): print(c) 

['f', 'o', 'obar'] 
['f', 'oo', 'bar'] 
['f', 'oob', 'ar'] 
['f', 'ooba', 'r'] 
['fo', 'o', 'bar'] 
['fo', 'ob', 'ar'] 
['fo', 'oba', 'r'] 
['foo', 'b', 'ar'] 
['foo', 'ba', 'r'] 
['foob', 'a', 'r'] 

我選擇，因爲你基本上是在組合談論compositions名稱「組成」。我的算法是基於鏈接文章中的證明，即將n個項目組合成k個片段的數量爲C(n-1,k-1)。

Answer 2

看看Word break算法，這是一個變體，它有一個明顯的區別，即單詞不是來自預定義的字典，而是需要在最終集合中有一個固定數量的算法。

主要思想是從頭開始遍歷輸入，切片並遞歸處理右部分。

假設函數原型

def rec(input, n): 

這是一個僞代碼：使用

if n == 1: 
    final_set.append([input[i:]]) 
else: 
    for i in range (0, len(input) - n + 1): 
     for rec_set in rec(input[i:], n - 1): 
      final_set.append(merge(input[:i], rec_set)) 

你的榜樣，我們有：

rec('foobar', 3) 
= {['f', rec('oobar', 2)], ['fo', rec('obar', 2)], ['foo', rec('bar', 2)], ['foob', rec('ar', 2)]} 

= {['f','o', rec('obar', 1)], ['f','oo', rec('bar', 1)], ['f','oob', rec('ar', 1)], ['f','ooba', rec('r', 1)], ['fo', 'o', rec('bar', 1)], ['fo', 'ob', rec('ar', 1)], ['fo', 'oba', rec('r', 1)], ['foo', 'b', rec('ar', 1)], ['foo', 'ba', rec('r', 1)], ['foob', 'a', rec('r', 1)]} 

= {['f','o', 'obar'], ['f','oo', 'bar'], ['f','oob', 'ar'], ['f','ooba', 'r'], ['fo', 'o', 'bar'], ['fo', 'ob', 'ar'], ['fo', 'oba', 'r',], ['foo', 'b', 'ar'], ['foo', 'ba', 'r'], ['foob', 'a', 'r']} 

要記住的重要一點是到緩存部分結果爲了避免r重複做同樣的工作一遍又一遍。例如，如果您已經計算出rec('oobar', 2)將結果存儲在某個緩存中（例如字典適用於此），並在函數的開頭檢查是否已經計算了指定輸入字符串和n的所有可能組合。它將時間複雜度從指數式降低到多項式。

Answer 3

您可以使用backtracking。只要您將單詞分成三部分以上，就會生成所有可能的分割和回溯。

Answer 4

下面是一個簡單而又重複的

def split(s, n): 
    def rec_split(i, s, n): 
     ans = [] 

     if n == 1: 
      ans.append([s[i:]]) 
      return ans 

     for j in range(i+1, len(s)): 
      head = s[i:j] 
      tails = rec_split(j, s, n-1) 
      for tail in tails: 
       ans.append([head] + tail) 
     return ans 

    return rec_split(0, s, n) 

for e in split("foobar", 3): 
    print(e) 

# ['f', 'o', 'obar'] 
# ['f', 'oo', 'bar'] 
# ['f', 'oob', 'ar'] 
# ['f', 'ooba', 'r'] 
# ['fo', 'o', 'bar'] 
# ['fo', 'ob', 'ar'] 
# ['fo', 'oba', 'r'] 
# ['foo', 'b', 'ar'] 
# ['foo', 'ba', 'r'] 
# ['foob', 'a', 'r'] 

rec_split回報n部分從i個指標的s所有分區以後

Answer 5

就可以解決這個遞歸與發電機：

def sections(s, n): 
    if n == 1: 
     yield [s] 

    if n > 1: 
     for i in range(1, len(s)): 
      for tail in section(s[i:], n - 1): 
       yield [s[0:i]] + tail 

並像這樣使用它：

for s in sections("foobar", 3): 
    print s