Python置换生成器拼图

Question

我正在编写一个置换函数，它用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

Answer 1

您还必须生成递归调用的结果：

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

..。或者(更接近操作码)：

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

Answer 2

当你做流行音乐的时候，你正在破坏性地丢失物品。使用列表的副本，而不是就地改变它。

或者，使用itertools.permutations或itertools.combinations。