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

Недавно я написал функцию для генерации определенных последовательностей с нетривиальными ограничениями. Проблема заключалась в естественном рекурсивном решении. Теперь случается, что даже для относительно небольшого ввода последовательности составляют несколько тысяч, поэтому я предпочел бы использовать мой алгоритм в качестве генератора вместо того, чтобы использовать его для заполнения списка всеми последовательностями.

Вот пример. Предположим, мы хотим вычислить все перестановки строки с рекурсивной функцией. Следующий наивный алгоритм принимает дополнительный аргумент "хранилище" и добавляет к нему перестановку всякий раз, когда он находит одно:

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

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

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

Ответы

Ответ 1

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

Ответ 2

Это позволяет избежать рекурсии 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 добавит 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])

Ответ 3

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