代码之家 › 专栏 › 技术社区 › Federico A. Ramponi

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

generator recursion python

Federico A. Ramponi · 技术社区 · 16 年前

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

下面是一个例子。假设我们要用递归函数计算字符串的所有排列。下面的naive算法接受一个额外的参数“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 回复 | 直到 12 年前

117

Markus Jarderot 16 年前

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

ephemient 12 年前

这避免了 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 而不是通过它迭代, 产量 手动操作每个项目。

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

Markus Jarderot 13 年前

内部调用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 posting,它以秒为单位将我排除在外!)