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

你在使用 pop 的时候，会把列表里的项目给删掉，这样就损失了数据。建议你使用列表的副本，而不是直接修改原来的列表。

另外，你也可以使用 itertools.permutations 或 itertools.combinations 这些工具来处理。

Answer 2

你还需要把递归调用的结果返回出来：

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