python: использование рекурсивного алгоритма в качестве генератора

<p>недавно я написал функцию для генерации определенных последовательностей с нетривиальными ограничениями. проблема пришла с естественным рекурсивным решением. теперь случается так, что даже при относительно небольших входных данных последовательности составляют несколько тысяч, поэтому я предпочел бы использовать мой алгоритм в качестве генератора, а не использовать его для заполнения списка всеми последовательностями.</p><p>вот пример. предположим, мы хотим вычислить все перестановки строки с помощью рекурсивной функции. следующий наивный алгоритм принимает дополнительный аргумент "storage" и добавляет к нему перестановку всякий раз, когда он его находит:</p><pre><code>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 </code></pre><p>(пожалуйста, не заботьтесь о неэффективности, это только пример.)</p><p>теперь я хочу превратить свою функцию в генератор, то есть получить перестановку вместо добавления ее в список хранения:</p><pre><code>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 </code></pre><p>этот код работает <em>не</em> (функция ведет себя как пустой генератор).</p><p>я что-то пропустил? есть ли способ превратить вышеуказанный рекурсивный алгоритм в генератор <em>не заменяя его на итеративный</em>?</p>

<pre><code>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 </code></pre><p>или без аккумулятора:</p><pre><code>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 </code></pre>

<p>это позволяет избежать глубокой рекурсии <code>len(string)</code>- и, в общем, является хорошим способом обработки генераторов внутри генераторов:</p><pre><code>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 </code></pre><p><code>flatten</code> позволяет нам продолжать прогресс в другом генераторе, просто <code>yield</code>ing его, вместо итерации по нему и <code>yield</code>ing каждого элемента вручную.</p><hr><p>python 3.3 добавит <a href="http://docs.python.org/dev/whatsnew/3.3.html#pep-380-syntax-for-delegating-to-a-subgenerator"><code>yield from</code></a> к синтаксису, что позволяет естественное делегирование субгенератору:</p><pre><code>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]) </code></pre>

<p>внутренний вызов getpermutations - это тоже генератор.</p><pre><code>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]) # <----- </code></pre><p>вам нужно повторить это с помощью цикла for (см. публикацию @mizardx, которая меня затянула на несколько секунд!)</p>