递归生成器

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中编写递归生成器的方法,还是有更好的(更惯用,更高性能等)替代方案？

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",但底部有一个链接,以更灵活和优化(但更难理解)版本.它似乎并没有实际工作(我得到NameError的_stack,但它看起来像它应该是很容易解决.如果是的话,如果它是可以接受把一个@supergenerator装饰上最发生器,如果表现尚可,有你回答.

如果没有,你可以采取各种技巧来处理多个级别的产量循环,而不是在每个级别.但是,它们都不会让你降到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),测试地狱出来,释放它,然后有人叫comb上一tuple...)的治疗比疾病,这就是为什么我把它叫做一招更糟糕.

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

只是为了好玩,我写了一首全能唱歌 - 全能舞蹈 - 任何你想要的方式,并将其作为补丁提交给Erik Rose的漂亮的更多 - itertools库.即使他不接受它,你也可以在我的fork -it中找到它collapse,它是文件中的最后一个函数.