无限生成器的Python产品

2023-02-25 16:30:21

我试图获得2个无限生成器的产品,但产品函数在itertools doesn’t allow this中的行为.

示例行为：

from itertools import *
i = count(1)
j = count(1)
x = product(i, j)

[Killed]

我想要的是：

x = product(i, j)

((0,0), (0,1), (1,0), (1,1) ...)

只要给定无限时间,组合返回的顺序无关紧要,最终将生成所有组合.这意味着给定元素组合,返回的生成器中必须有一个有限的索引.

解决方法:

TL;博士

下面给出的代码现在包含在PyPI上的包infinite中.所以现在你可以在运行之前实际上只是pip install infinite：

from itertools import count
from infinite import product

for x, y in product(count(0), count(0)):
    print(x, y)
    if (x, y) == (3, 3):
        break

懒惰的解决方案

如果您不关心订单,由于生成器是无限的,有效的输出将是：

(a0, b1), (a0, b2), (a0, b3), ... (a0, bn), ...

所以你可以从第一个生成器中获取第一个元素,然后遍历第二个元素.

如果你真的想要这样做,你需要一个嵌套循环,你需要用tee复制嵌套的生成器,否则你将无法再次循环它(即使它无关紧要因为你永远不会排气发电机,所以你永远不需要循环).

但如果你真的真的想要这样做,你可以在这里：

from itertools import tee

def product(gen1, gen2):
    for elem1 in gen1:
        gen2, gen2_copy = tee(gen2)
        for elem2 in gen2_copy:
            yield (elem1, elem2)

我们的想法是始终制作gen2的单一副本.首先尝试使用有限生成器.

print(list(product(range(3), range(3,5))))
[(0, 3), (0, 4), (1, 3), (1, 4), (2, 3), (2, 4)]

然后是无限的：

print(next(product(count(1), count(1))))
(1, 1)

之字形算法

正如评论中的其他人所指出的那样(并且如前面的解决方案中所述),这不会产生所有组合.然而,自然数和数字对之间的映射存在,因此必须能够以不同的方式迭代对,以便在有限的时间内完成寻找特定对(没有无限数),你需要zig- zag扫描算法.

为了做到这一点,你需要缓存以前的值,所以我创建了一个类GenCacher来缓存以前提取的值：

class GenCacher:
    def __init__(self, generator):
        self._g = generator
        self._cache = []

    def __getitem__(self, idx):
        while len(self._cache) <= idx:
            self._cache.append(next(self._g))
        return self._cache[idx]

之后,您只需要实现Zig-zag算法：

def product(gen1, gen2):
    gc1 = GenCacher(gen1)
    gc2 = GenCacher(gen2)
    idx1 = idx2 = 0
    moving_up = True

    while True:
        yield (gc1[idx1], gc2[idx2])

        if moving_up and idx1 == 0:
            idx2 += 1
            moving_up = False
        elif not moving_up and idx2 == 0:
            idx1 += 1
            moving_up = True
        elif moving_up:
            idx1, idx2 = idx1 - 1, idx2 + 1
        else:
            idx1, idx2 = idx1 + 1, idx2 - 1

例

from itertools import count

for x, y in product(count(0), count(0)):
    print(x, y)
    if x == 2 and y == 2:
        break

这会产生以下输出：

将解决方案扩展到2个以上的发电机

我们可以稍微编辑解决方案,使其即使对于多个生成器也能工作.基本思路是：

>迭代距离(0,0)(索引之和)的距离. (0,0)是距离为0的唯一一个,(1,0)和(0,1)距离为1,等等.
>为该距离生成所有索引元组
>提取相应的元素

我们仍然需要GenCacher类,但代码变为：

def summations(sumTo, n=2):
    if n == 1:
        yield (sumTo,)
    else:
        for head in xrange(sumTo + 1):
            for tail in summations(sumTo - head, n - 1):
                yield (head,) + tail

def product(*gens):
    gens = map(GenCacher, gens)

    for dist in count(0):
        for idxs in summations(dist, len(gens)):
            yield tuple(gen[idx] for gen, idx in zip(gens, idxs))

码农公寓

相关文章