Python:使用递归算法作为生成器
Python:使用递归算法作为生成器
提问于 2008-10-29 23:45:56
最近，我编写了一个函数来生成具有非平凡约束的特定序列。这个问题有一个自然的递归解决方案。现在，即使对于相对较小的输入，序列也有数千个，因此我更喜欢使用我的算法作为生成器，而不是使用它来填充所有序列的列表。
下面是一个例子。假设我们想用一个递归函数计算一个字符串的所有排列。下面的朴素算法接受一个额外的参数'storage‘，并在找到时将一个排列附加到该参数后面：
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此代码不起作用(该函数的行为类似于空生成器)。
我是不是遗漏了什么？有没有一种方法可以把上面的递归算法变成一个生成器，而不用迭代算法来代替它
回答 3
Stack Overflow用户
回答已采纳
发布于 2008-10-29 23:53:48
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] + permStack Overflow用户
发布于 2008-10-31 00:05:38
这避免了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 permutationflatten允许我们在另一个生成器中继续前进，只需简单地yield它，而不是遍历它并手动yield每一项。
Python3.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])Stack Overflow用户
发布于 2008-10-29 23:54:52
内部调用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帖子，它比我快了几秒钟！)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/248830
复制相关文章
相似问题