Python: использование рекурсивного алгоритма в качестве генератора
Вопрос
Недавно я написал функцию для генерации определенных последовательностей с нетривиальными ограничениями. Проблема пришла с естественным рекурсивным решением. Теперь случается, что даже при относительно небольших входных данных последовательности составляют несколько тысяч, поэтому я предпочел бы использовать мой алгоритм в качестве генератора, а не использовать его для заполнения списка всеми последовательностями.
Вот пример. Предположим, мы хотим вычислить все перестановки строки с помощью рекурсивной функции. Следующий наивный алгоритм принимает дополнительный аргумент «storage» и добавляет к нему перестановку всякий раз, когда он его находит:
def getPermutations(string, storage, prefix=""):
if len(string) == 1:
storage.append(prefix + string) # <-----
else:
for i in range(len(string)):
getPermutations(string[:i]+string[i+1:], storage, prefix+string[i])
storage = []
getPermutations("abcd", storage)
for permutation in storage: print permutation
(Пожалуйста, не заботьтесь о неэффективности, это только пример.)
Теперь я хочу превратить свою функцию в генератор, т. е. получить перестановку вместо добавления ее в список хранения:
def getPermutations(string, prefix=""):
if len(string) == 1:
yield prefix + string # <-----
else:
for i in range(len(string)):
getPermutations(string[:i]+string[i+1:], prefix+string[i])
for permutation in getPermutations("abcd"):
print permutation
Этот код не работает (функция ведет себя как пустой генератор).
Я что-то упустил? Есть ли способ превратить вышеуказанный рекурсивный алгоритм в генератор , не заменяя его на итеративный ?
Решение
def getPermutations(string, prefix=""):
if len(string) == 1:
yield prefix + string
else:
for i in xrange(len(string)):
for perm in getPermutations(string[:i] + string[i+1:], prefix+string[i]):
yield perm
Или без аккумулятора:
def getPermutations(string):
if len(string) == 1:
yield string
else:
for i in xrange(len(string)):
for perm in getPermutations(string[:i] + string[i+1:]):
yield string[i] + perm
Другие советы
Это позволяет избежать рекурсии len (string)
-deep и, в общем, является хорошим способом работы с генераторами внутри генераторов:
from types import GeneratorType
def flatten(*stack):
stack = list(stack)
while stack:
try: x = stack[0].next()
except StopIteration:
stack.pop(0)
continue
if isinstance(x, GeneratorType): stack.insert(0, x)
else: yield x
def _getPermutations(string, prefix=""):
if len(string) == 1: yield prefix + string
else: yield (_getPermutations(string[:i]+string[i+1:], prefix+string[i])
for i in range(len(string)))
def getPermutations(string): return flatten(_getPermutations(string))
for permutation in getPermutations("abcd"): print permutation
flatten
позволяет нам продолжать прогресс в другом генераторе, просто yield
, вместо того, чтобы выполнять его итерацию и yield
каждый элемент вручную . р>
<Ч>
Python 3.3 добавит уступить
синтаксису, который позволяет естественное делегирование суб-генератору:
def getPermutations(string, prefix=""):
if len(string) == 1:
yield prefix + string
else:
for i in range(len(string)):
yield from getPermutations(string[:i]+string[i+1:], prefix+string[i])
Внутренний вызов getPermutations - это тоже генератор.
def getPermutations(string, prefix=""):
if len(string) == 1:
yield prefix + string
else:
for i in range(len(string)):
getPermutations(string[:i]+string[i+1:], prefix+string[i]) # <-----
Вам нужно повторить это с помощью цикла for (см. публикацию @MizardX, которая меня затянула на секунды!)