Python permutation generator puzzle

Question

I am writing a permutation function that generate all permutations of a list in Python. My question is why this works:

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],[])

But this does not:

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

This does not work either (yield a copy of the list):

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

You're destructively losing items when you do the pop. Use copies of the list instead of mutating it in-place.

Alternately, use itertools.permutations or itertools.combinations instead.

Answer 2

You must also yield the results of the recursive call(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

... Or (closer to the OP code):

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