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

10 浏览
0 Comments

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

最近我写了一个函数来生成满足非平凡约束条件的序列。这个问题有一个自然的递归解法。现在的问题是，即使对于相对较小的输入，生成的序列也有几千个，因此我更愿意将我的算法作为生成器使用，而不是用它来填充一个包含所有序列的列表。

下面是一个例子。假设我们想要使用递归函数计算一个字符串的所有排列。下面这个简单的算法使用了一个额外的参数“storage”，并在找到一个排列时将其附加到“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

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

我有什么遗漏的地方吗？

有没有办法将上面的递归算法改造成一个生成器，而不是用迭代算法替代它？

0