Python：使用recursionalgorithm作为生成器

最近我写了一个函数来生成具有非平凡约束的特定序列。 问题出现在一个自然的recursion解决scheme中。 现在碰巧，即使是相对较小的input，序列也是几千，所以我宁愿使用我的algorithm作为生成器，而不是用它来填充所有序列的列表。

这是一个例子。 假设我们想要用recursion函数计算一个string的所有排列。 下面的朴素algorithm需要一个额外的参数“存储”，并且每当它find一个时就附加一个排列：

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 

此代码不起作用（该函数的行为像一个空的发电机）。

我错过了什么吗？ 有没有办法把上面的recursionalgorithm变成一个生成器而不用迭代迭代呢？

Answer 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 

Answer 2

这避免了len(string)深度recursion，并且通常是处理generator-inside-generators中的一个好方法：

 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语法中增加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]) 

Answer 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的发布，这让我几秒钟就到了）。