Python：将递归算法用作生成器

Question

最近我写了一个函数，用来生成一些有特殊限制的序列。这个问题有一个很自然的递归解决方案。不过，问题是，即使输入相对较小，生成的序列也有几千个，所以我更希望把我的算法当作生成器来用，而不是把所有序列都放到一个列表里。

举个例子。假设我们想用一个递归函数来计算一个字符串的所有排列。下面这个简单的算法多了一个参数'存储'，每当找到一个排列时，就把它加到这个存储里：

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

里面调用的 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 的帖子，他比我早了几秒钟！）

Answer 2

这样做可以避免使用 len(string) 进行深层递归，并且通常是处理生成器中生成器的一个不错的方法：

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

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

或者不使用累加器：