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置换生成器拼图

回答

相关问题