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
此代码不起作用（该函数的行为类似于空的生成器）。
我错过了什么吗？ 有没有办法将上面的递归算法变成一个生成器而不用迭代器替换它？
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
这避免了len(string)深度递归，并且通常是处理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 ，从而允许自然委派给子生成器：
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])
内部调用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发布，这让我几秒钟就可以完成）！
链接地址: http://www.djcxy.com/p/37283.html