Остановка рекурсивного генератора и перестановок - PullRequest
Новая
       45

Остановка рекурсивного генератора и перестановок

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

В качестве упражнения я пробовал различные способы генерации всех перестановок списка в Python - рекурсивных, нерекурсивных ... - и сравнения производительности с itertools.permutations().Но у меня возникли проблемы с версией генератора рекурсивного метода, которая не завершается чисто с исключением StopIteration, но вместо этого выдает 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:]

Вызов этого из 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

Ой.Я попытался пройти через него с помощью pdb, что почти создало переполнение стека в моем мозгу, но я понял, что рекурсия «доходит» до пустого списка, а затем запускается внешний (я думаю) цикл forвне индексов.

Как я могу исправить свой код?

РЕДАКТИРОВАТЬ: Из одного обманчиво простого правильного ответа Марка Байерса можно извлечь одно:ошибки .Если бы я систематически использовал else после if, независимо от того, думал ли я, что условие когда-либо будет пересмотрено, этого бы не случилось.И это все еще кажется очень глупым!

1 Ответ

6 голосов
/ 10 августа 2010

Вам не хватает else: 

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

Это потому, что yield не ведет себя так же, как return.Выполнение продолжается после оператора yield при запросе следующего значения.

...