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

这段代码并不起作用（函数的行为就像一个空生成器）。

我有什么遗漏吗？ 是否有一种方法可以将上述递归算法转换为生成器，而不是用迭代算法替换它？

- Federico Ramponi

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

- MizardX

---

在Python 3.4中，可以使用yield from getPermutations(string[:i] + string[i+1:])来替换最后两行代码，这种方式在多个方面上都更加高效！ - Manuel Ebert

你仍然需要以某种方式构建结果。使用 yield from 将要求您使用累加器参数（prefix）。 - Markus Jarderot

建议：定义另一个生成器，返回 string[i]，string[:i]+string[i+1:] 的一对。然后可以这样写：for letter,rest in first_letter_options(string): for perm in getPermuations(rest): yield letter+perm - Thomas Andrews

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

- ephemient

Answer 3

getPermutations这个内部调用也是一个generator。

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的帖子，他比我早几秒！）

- S.Lott