Python置換生成器拼圖

我正在編寫一個置換函數，它可以在Python中生成一個列表的所有排列組合。我的問題是，爲什麼這個工程：Python置換生成器拼圖

def permute(inputData, outputSoFar): 
    for elem in inputData: 
     if elem not in outputSoFar: 
      outputSoFar.append(elem) 
      if len(outputSoFar) == len(inputData): 
       print outputSoFar 
      else: 
       permute(inputData, outputSoFar) # --- Recursion 
      outputSoFar.pop() 

permute([1,2,3],[])

但這並不：

def permute(inputData, outputSoFar): 
    for elem in inputData: 
     if elem not in outputSoFar: 
      outputSoFar.append(elem) 
      if len(outputSoFar) == len(inputData): 
       yield outputSoFar 
      else: 
       permute(inputData, outputSoFar) # --- Recursion 
      outputSoFar.pop() 

for i in permute([1,2,3], []): 
    print i

這不工作，要麼（收率列表的副本）：

def permute(inputData, outputSoFar): 
    for elem in inputData: 
     if elem not in outputSoFar: 
      outputSoFar.append(elem) 
      if len(outputSoFar) == len(inputData): 
       yield outputSoFar[:] # --- Copy of the list 
      else: 
       permute(inputData, outputSoFar) # --- Recursion 
      outputSoFar.pop() 

for i in permute([1,2,3], []): 
    print i

來源

2010-08-05 Thanh DK

還必須得到遞歸調用（S）的結果：

def permute(inputData, outputSoFar): 
    for a in inputData: 
     if a not in outputSoFar: 
      if len(outputSoFar) == len(inputData) - 1: 
       yield outputSoFar + [a] 
      else: 
       for b in permute(inputData, outputSoFar + [a]): # --- Recursion 
        yield b 

for i in permute([1,2,3], []): 
    print i

...或者（更接近OP代碼）：

def permute(inputData, outputSoFar): 
    for elem in inputData: 
     if elem not in outputSoFar: 
      outputSoFar.append(elem) 
      if len(outputSoFar) == len(inputData): 
       yield outputSoFar 
      else: 
       for permutation in permute(inputData, outputSoFar): 
        yield permutation # --- Recursion 
      outputSoFar.pop() 

for i in permute([1,2,3], []): 
    print i

來源

2010-08-05 04:22:53

這工作，但我仍然不知道爲什麼我需要添加收益的遞歸調用。 – 2010-08-05 05:40:27

考慮第一個函數調用和條件（如果len（outputSoFar）== len（inputData），或者不）。第一次調用將會失敗（除非輸入中只有一個元素），所以它不會產生任何結果。相反，它必須依靠遞歸調用來查找排列，當它們這樣做時，它們將產生它們。但是，當它們返回到第一個函數調用時，它必須讓它們回到原始調用方。（每次遞歸，非基本情況下的調用都有類似的情況。）如果沒有這個，只有遞歸樹的葉子會產生任何東西。 – 2010-08-05 15:33:57

你當你做出流行音樂時會破壞性地丟失物品。使用列表的副本，而不是在原地進行變異。代替地，使用itertools.permutations或itertools.combinations代替。

來源

2010-08-05 04:07:16

-1：不正確的。追加和流行將會正常工作。 – 2010-08-05 04:38:53

所有新代碼itertools.permutations建議 – 2010-08-05 04:44:01

我知道itertools.permutation。然而，這個難題的目的是學習python生成器/遞歸。 – 2010-08-05 04:45:54

Python置換生成器拼圖

回答

相關問題