Python:使用递归算法作为生成器 [英] Python: using a recursive algorithm as a generator

问题描述

最近，我编写了一个函数来生成具有非平凡约束的某些序列.问题来自自然的递归解决方案.现在碰巧，即使对于相对较小的输入，序列也要成千上万，因此我宁愿使用我的算法作为生成器，而不是用它来填充所有序列的列表.

Recently I wrote a function to generate certain sequences with nontrivial constraints. The problem came with a natural recursive solution. Now it happens that, even for relatively small input, the sequences are several thousands, thus I would prefer to use my algorithm as a generator instead of using it to fill a list with all the sequences.

这里是一个例子.假设我们要使用递归函数计算字符串的所有排列.以下朴素算法采用一个额外的参数存储"，并在找到一个参数时附加一个置换:

Here is an example. Suppose we want to compute all the permutations of a string with a recursive function. The following naive algorithm takes an extra argument 'storage' and appends a permutation to it whenever it finds one:

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

(请不要在意效率低下，这只是一个例子.)

(Please don't care about inefficiency, this is only an example.)

现在，我想将函数转换为生成器，即产生一个置换，而不是将其追加到存储列表中:

Now I want to turn my function into a generator, i.e. to yield a permutation instead of appending it to the storage list:

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

此代码不起作用(该功能的行为就像一个空的生成器).

This code does not work (the function behaves like an empty generator).

我错过了什么吗? 有没有一种方法可以将上述递归算法转换为生成器，而不用迭代器替换它?

Am I missing something? Is there a way to turn the above recursive algorithm into a generator without replacing it with an iterative one?

推荐答案

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

这篇关于Python:使用递归算法作为生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！