Puzzle du générateur de permutation Python

J'écris une fonction de permutation qui génère toutes les permutations d'une liste en Python. Ma question est pourquoi cela fonctionne:Puzzle du générateur de permutation 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],[])

Mais cela ne:

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

Cela ne fonctionne pas non plus (obtenir une copie de la liste):

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

Source

2010-08-05 Thanh DK

Vous devez également donner les résultats de l'appel récursif (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

... Ou (plus près du code 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

Source

2010-08-05 04:22:53

Cela fonctionne mais je ne sais toujours pas pourquoi j'ai besoin d'ajouter le rendement à l'appel récursif. –

Considérons le premier appel de fonction et la condition (si len (outputSoFar) == len (inputData), ou pas). Le premier appel échouera à la condition (à moins qu'il n'y ait qu'un seul élément dans l'entrée), donc il ne donnera rien. Au lieu de cela, il doit s'appuyer sur des appels récursifs pour trouver des permutations, et quand ils le font, ils vont les céder. Cependant, lorsqu'ils sont restitués à cet appel de première fonction, ils doivent les restituer à l'appelant d'origine. (Chaque appel récursif, non-base-cas est dans une situation similaire.) Sans cela, seules les feuilles de l'arbre de récursion donneront n'importe quoi. –

Vous êtes perdre des objets destructivement quand vous faites le pop. Utilisez des copies de la liste au lieu de la faire muter sur place.

Alternativement, utilisez itertools.permutations ou itertools.combinations à la place.

Source

2010-08-05 04:07:16

-1: pas vrai. Ajouter et pop fonctionnera bien. –

pour tout nouveau code itertools.permutations est recommandé –

Je sais à propos de itertools.permutation. Cependant, le but de ce puzzle est de se renseigner sur le générateur/récursion de python. –

Puzzle du générateur de permutation Python

Répondre

Questions connexes