递归生成器

Question

我时常在Python中编写递归生成器。以下是一个最近的例子：

def comb(input, lst = [], lset = set()):
   if lst:
      yield lst
   for i, el in enumerate(input):
      if lset.isdisjoint(el):
         for out in comb(input[i+1:], lst + [el], lset | set(el)):
            yield out

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

算法的细节并不重要。我将其包含在内作为一个完整的、现实世界的例子，以便给问题一些背景。

我的问题是关于以下结构的：

   for out in comb(...):
      yield out

comb()是生成器的递归实例化。

每次我必须拼写出for:yield循环，这让我感到不满意。这真的是在Python中编写递归生成器的最佳方式吗？还是有更好的选择（更符合惯用法、性能更好等）？

- NPE

---

Python 3.3引入了yield from <generator>语法结构，但目前尚未将其移植回早期版本。 - Wessie

在Py3.3上使用新的yield from语法。它是为这些事情而设计的。 - JBernardo

哦，太棒了！可惜我还在使用Python 2.x. :( - NPE

@Wessie：+1，但是……“尚未回溯到现在”？您预计将其回撤到何时，以及回滚到哪个版本？没有未来的发布版本可以进行回溯。 - abarnert

在Python2.7中，那也是我通常做的。 - jdotjdot

@abarnert: 你说得对，它不会被回溯到早期版本的语言构造中。不过我记得有一个纯Python实现 Pure Python yield from。请参考。 - Wessie

Answer 1

每次我不得不拼写for：yield循环时，都会让我感到不舒服。这真的是在Python中编写递归生成器的方式吗？还是有更好的（更习惯用的、性能更好的等）替代方案？

有一个更好的替代方案：

yield from comb(...)

这实际上与以下操作相同：

for out in comb(...):
    yield out

这需要Python 3.3。如果你还在使用Python 2.x（或旧版的3.x），你必须坚持使用旧方法，因为Python 2的语法在2.7之后将永远不会再更新（而3.0到3.2显然也是一样的）。

首先，请查看Wessie在评论中提到的纯Python yield from。此版本仅适用于单个级别的“yield from”，但底部有一个链接指向更灵活和优化的（但更难理解的）版本。它似乎并没有实际工作（我在_stack上得到了一个NameError，但看起来应该很容易修复。如果可以，在最外层生成器上放置一个@supergenerator装饰器，并且性能可接受，则有您的答案。

如果不行，有各种技巧可以处理多个级别的yield循环，而不是在每个级别上进行处理。但是，它们中没有一个可以将您降至0级，而且真的很少值得做。例如：

一旦您考虑到序列而不是生成器函数，就很明显我们所要做的就是展平一个序列。无论您要展平N级，展平到达非可迭代的级别，展平满足其他可预测条件等，都有一个简单的算法；您只需要选择正确的算法。但是它会使您的代码更符合惯例、可读性更强、性能更好吗？很少。让我们看一个超级简单的情况。

def flatten(seq, levels=1):
    for level in range(levels):
        seq = itertools.chain.from_iterable(seq)
    return seq

所以：

def a():
    yield 1
    yield 2
    yield 3
def b():
    yield a()
def c():
    yield b()
def d():
    yield c()

for i in flatten(d(), 3):
    print i

好处是我只需要在一个地方处理嵌套，即调用站点，而不是在每个生成器的3个位置处理。代价是对读者来说不太明显发生了什么，并且更容易出错。(好吧，在这种情况下不太可能...但想象一下展开直到lambda x: isinstance(list)，对其进行大量测试，发布它，然后有人在tuple上调用comb...)治疗比疾病更糟糕，这就是为什么我称之为技巧。

除非展开确实是算法的自然部分，或者某些中间步骤是您不能或不想触摸的代码，或者以这种方式构造事物是有用的说明或提醒，或者...

只是为了好玩，我编写了一个全唱全跳的任意展平函数，并将其提交为Erik Rose的漂亮的more-itertools库的补丁。即使他不接受它，您也可以在我的分支中找到它——它被称为collapse，并且是文件中的最后一个函数。

- abarnert