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

此代码执行 没有工作(该函数的行为类似于空生成器)。

我错过了什么吗？ 有没有办法把上面的递归算法变成一个生成器 而不是用一个迭代来代替它？

35168 次浏览
小开
最佳答案 
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

Or without an accumulator:

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
小开

The interior call to getPermutations -- it's a generator, too.

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])  # <-----

You need to iterate through that with a for-loop (see @MizardX posting, which edged me out by seconds!)

小开

This avoids the len(string)-deep recursion, and is in general a nice way to handle generators-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 allows us to continue progress in another generator by simply yielding it, instead of iterating through it and yielding each item manually.

Python 3.3 will add yield from to the syntax, which allows for natural delegation to a sub-generator:

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])

提交答案