python - 使用 izip 的 Python 递归生成器中的意外行为

Question

我编写了一个名为 size_subsets 的函数，当传递城市(数字)列表时，该函数返回特定大小的所有子集。但是，使用 izip() 而不是两个 for-yield block 重新声明该函数会完全破坏该行为。

下面的第二个方法使用 izip() 重述了第一个方法，但由于某种原因它在顶层没有返回任何内容。谁能帮我弄清楚这是为什么？

打印语句显示，一些(不是全部)正确的子集确实在 size_subsets_broken 中递归的最底层生成，但即使这些也没有使其到达顶层由于某种原因。

def size_subsets(cities, size, sofar):
    if not size:
        yield sofar
        return
    elif len(cities) < size:
        return
    else:
        curr_city = cities.pop()
        for a in size_subsets(cities[:], size - 1, sofar | {curr_city}):
            yield a
        for b in size_subsets(cities[:], size, sofar):
            yield b


def size_subsets_broken(cities, size, sofar):
    if not size:
        yield sofar
        return
    elif len(cities) < size:
        return
    else:
        curr_city = cities.pop()
        inclusive = size_subsets_broken(cities[:], size - 1, sofar | {curr_city})
        exclusive = size_subsets_broken(cities[:], size, sofar)

        for incl_subset, excl_subset in izip(inclusive, exclusive):
            yield incl_subset
            yield excl_subset


print list(size_subsets([1, 2, 3], 2, set()))           # [set([2, 3]), set([1, 3]), set([1, 2])]
print list(size_subsets_broken([1, 2, 3], 2, set()))    # []

Answer 1

我怀疑你误解了 izip()作品。当最短输入迭代耗尽时，它只是简单地停止，并且没有理由相信您的 inclusive和exclusive始终具有相同的长度。

>>> from itertools import izip
>>> for i in izip(range(10), [6]):
...     print i
(0, 6)

>>> for i in izip(range(10), []):
...     print i

请注意，第一个示例中只有一个输出，第二个示例中根本没有输出。这都是预料之中的。

详细信息

顶级调用size_subsets_broken()创建一个生成器迭代器 ( gi ) 对象。调用list()迫使后者做某事。

它创建 inclusive和exclusive gi带有参数的对象(忽略 sofar ) [1, 2], 1和[1, 2], 2 。 izip()然后尝试将它们组合起来。

izip()首先尝试从 inclusive 获取值(最终无法提供任何东西，这就是为什么顶级 gi 也永远不会产生任何东西 - 事实上，它甚至从未尝试强制 exclusive 产生任何东西，因为 inclusive 是空的 - izip() “只是当最短的输入迭代耗尽时，plain 就会停止”)。

回想一下顶级 inclusive 的参数是[1, 2], 1 。它创建gi [1], 0 的对象和[1], 1 。 它 izip()推[1], 0分支以产生一个值，它通过 if not size 执行此操作。测试。所以它是izip()继续插入[1], 1分支一个值。

这又创建了 [], 0和[], 1 gi分支机构。另一层izip()插入其中第一个分支产生一个值(再次通过 if not size 测试)，但第二个分支不会产生任何值，因为 if len(cities) < size: return 。所以izip()向上一级放弃，gi它属于什么也不产生。

它沿着链向上传播:在每个级别，izip()找到至少一个空迭代器，因此 for ... in izip(...): 的主体永远不会进入循环(在任何级别)。

这不是 izip() 的问题， 顺便一提。 尝试使用 izip() 根本没有意义。在这个算法中。