Python:使用递归算法作为生成器

Question

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

这是一个例子.假设我们想用递归函数计算字符串的所有排列.以下天真算法需要额外的参数'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

此代码不能正常工作(该函数的行为像一个空发生器).

我错过了什么吗？有没有办法将上述递归算法转换为生成器而不用迭代算法替换它？

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

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发布,这让我几秒钟!)