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

Question

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

этот код не работа (функция ведет себя как пустой генератора).

Я что-то пропустила?
Есть есть способ превратить приведенный выше рекурсивный алгоритм в генератор без замены его итерационным?

1137 3

python recursion generator

3 ответов:

Comments

Ничего не найдено.

Markus Jarderot · Accepted Answer · 2008-10-30 01:53:47

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

ephemient · Accepted Answer · 2012-08-13 15:29:36

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

Python 3.3 добавит yield from "синтаксис", который позволяет естественным делегации в суб-генератор:
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])

S.Lott · Accepted Answer · 2012-02-16 00:01:54

внутренний вызов 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 posting, который обошел меня на несколько секунд!)