Пазл генератор перестановок Python - PullRequest
Новая
       70

Пазл генератор перестановок Python

0 голосов
/ 05 августа 2010

Я пишу функцию перестановки, которая генерирует все перестановки списка в 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

Ответы [ 2 ]

3 голосов
/ 05 августа 2010

Вы также должны выдать результаты рекурсивных вызовов: 

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
0 голосов
/ 05 августа 2010

Вы разрушаете вещи, когда вы делаете поп-музыку.Используйте копии списка вместо того, чтобы менять его на месте.

В качестве альтернативы используйте itertools.permutations или itertools.combinations вместо.

...