Arrêt d'un générateur récursif & permutations

Question

A titre d'exercice, j'ai essayé différentes façons de générer toutes les permutations d'une liste en Python - récursif, non récursif ... - et en comparant les performances avec itertools.permutations(). Mais je vais avoir des problèmes avec la version du générateur de la méthode récursive, qui ne se termine pas proprement à une exception StopIteration, mais les lancers francs à la place un IndexError:

def spawnperms(alist): 
    """same algorithm as recursive option, but a generator""" 
    if (alist == []): 
     yield [] 
    for perm in spawnperms(alist[:-1]): 
     for i in range(len(perm)+1): 
      yield perm[:i] + [alist[-1]] + perm[i:] 

Appeler cela de l'interpréteur Python:

>>> for i in spawnperms(range(3)): 
...  print i 
... 
[2, 1, 0] 
[1, 2, 0] 
[1, 0, 2] 
[2, 0, 1] 
[0, 2, 1] 
[0, 1, 2] 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 7, in spawnperms 
IndexError: list index out of range 

Ouch. J'ai essayé de le franchir avec pdb, ce qui a presque créé un débordement de pile dans mon cerveau, mais ce que j'ai compris, c'est que la récursion «descend» vers la liste vide, et la boucle externe (à mon avis) manque d'index.

Comment puis-je corriger mon code?

EDIT: Un apprentissage de réponse trompeusement simple Mark Byers est que pratiques de codage propres peuvent éviter les erreurs. Avais-je utilisé un else systématiquement après if, indépendamment du fait que je pensais que la condition pourrait jamais être revisitée, cela ne serait pas arrivé. Et il se sent toujours très stupide!

Answer 1

Il vous manque un else:

if (alist == []): 
    yield [] 
else: 
    for ... 

C'est parce que yield ne se comporte pas de la même manière que return. L'exécution se poursuit après l'instruction yield lorsque vous demandez la valeur suivante.