Недавно я написал функцию для создания определенных последовательностей с нетривиальными ограничениями. Проблема пришла с естественным рекурсивным решением. Теперь получается, что даже для относительно небольшого ввода последовательностей несколько тысяч, поэтому я бы предпочел использовать мой алгоритм в качестве генератора, а не использовать его для заполнения списка всеми последовательностями.
Вот пример. Предположим, мы хотим вычислить все перестановки строки с помощью рекурсивной функции. Следующий наивный алгоритм принимает дополнительный аргумент «хранилище» и добавляет к нему перестановку всякий раз, когда находит его:
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) для перестановки в хранилище: распечатать перестановку (Пожалуйста, не беспокойтесь о неэффективности, это всего лишь пример.)
Теперь я хочу превратить свою функцию в генератор, т.е. получить перестановку вместо добавления ее в список хранения:
def getPermutations(string , prefix=""): если len(string) == 1: yield prefix + string # <----- else: for i in range(len(string)): getPermutations(string[:i]+string [i+1:], prefix+string[i]) для перестановки в getPermutations("abcd"): напечатать перестановку Этот код не работает ( функция ведет себя как em генератор pty).
Я что-то упустил? Есть ли способ превратить приведенный выше рекурсивный алгоритм в генератор, не заменяя его итеративным?