Недавно я написал функцию для генерации определенных последовательностей с нетривиальными ограничениями. Проблема заключалась в естественном рекурсивном решении. Теперь случается, что даже для относительно небольшого ввода последовательности составляют несколько тысяч, поэтому я предпочел бы использовать мой алгоритм в качестве генератора вместо того, чтобы использовать его для заполнения списка всеми последовательностями.
Вот пример. Предположим, мы хотим вычислить все перестановки строки с рекурсивной функцией. Следующий наивный алгоритм принимает дополнительный аргумент "хранилище" и добавляет к нему перестановку всякий раз, когда он находит одно:
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
Этот код не работает (функция ведет себя как пустой генератор).
Я что-то упустил? Есть ли способ превратить вышеуказанный рекурсивный алгоритм в генератор, не заменяя его итеративным?