Python无穷生成器的乘积

Question

我正在尝试获取2个无限生成器的乘积，但是itertools中的product函数不允许此类行为。

示例行为：

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) ...)

无论组合以何种顺序返回，只要有无限时间，所有组合最终都会生成。这意味着，对于一组元素的组合，返回的生成器中必须有一个有限的索引与该组合相对应。

- muddyfish

---

你可能会对 coconut-lang 感兴趣。在这里查看一个类似于你想要的示例：http://coconut.readthedocs.io/en/master/HELP.html#case-study-4-vector-field。 - Ilya V. Schurov

Answer 1

简述

下面的代码现在已经包含在了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)]

然后使用无限个“1”：

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

锯齿形扫描算法

正如评论中其他人所指出的那样（并且在先前的解决方案中已经说明），这不会产生所有的组合。尽管如此，自然数和数字对之间的映射是存在的，因此必须以不同的方式迭代数字对，以便在有限时间内查找特定的数字对（而无需无限数字）。你需要使用锯齿形扫描算法。

为了实现它，您需要缓存先前的值，因此我创建了一个名为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

这将产生以下输出：

0 0
0 1
1 0
2 0
1 1
0 2
0 3
1 2
2 1
3 0
4 0
3 1
2 2

将解决方案扩展到多个发生器

我们可以稍微修改解决方案，使其适用于多个发生器。基本思路是：

1. 迭代从(0,0)（索引之和）开始的距离。(0,0)是唯一一个距离为0的点，(1,0)和(0,1)距离为1，以此类推。

2. 生成该距离下的所有索引元组。

3. 提取相应的元素。

我们仍然需要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))

- enrico.bacis

---

它们永远不会被生成。你正在处理无限。你应该指定顺序，否则任何解决方案都可以接受。我建议您使用锯齿形顺序。 - enrico.bacis

你确定这样会列出所有的吗？看起来第二个循环永远不会结束。 - muddyfish

@enrico.bacis，那不正确。对于Zig-Zag枚举，对于产品集中的任何元素，都存在某个自然数N，使得该元素是序列中的第N个。在您的示例中，大多数元素都没有这样的N。 - Ilya V. Schurov

@所有人请注意，我已经实现了Zig-Zag算法，现在它按预期工作。 - enrico.bacis

@muddyfish 现在它应该按照你的期望执行。 - enrico.bacis

Answer 2

 def product(a, b):
     a, a_copy = itertools.tee(a, 2)
     b, b_copy = itertools.tee(b, 2)
     yield (next(a_copy), next(b_copy))
     size = 1
     while 1:
         next_a = next(a_copy)
         next_b = next(b_copy)
         a, new_a = itertools.tee(a, 2)
         b, new_b = itertools.tee(b, 2)
         yield from ((next(new_a), next_b) for i in range(size))
         yield from ((next_a, next(new_b)) for i in range(size))
         yield (next_a, next_b)
         size += 1

使用itertools.tee的自制解决方案。由于中间状态存储在tee中，因此会消耗大量内存。

这有效地返回一个不断扩展的正方形的边：

0 1 4 9 
2 3 5 a
6 7 8 b
c d e f

如果有无限的时间和内存，这个实现“应该”返回所有可能的乘积。

- muddyfish

Answer 3

无论你如何做，内存都会增长很多，因为每个迭代器中的每个值在第一次之后都会出现无限次数，所以必须将其保存在某个不断增长的变量中。

因此，像这样的东西可能有效：

def product(i, j):
    """Generate Cartesian product i x j; potentially uses a lot of memory."""
    earlier_values_i = []
    earlier_values_j = []

    # If either of these fails, that sequence is empty, and so is the
    # expected result. So it is correct that StopIteration is raised,
    # no need to do anything.
    next_i = next(i)
    next_j = next(j)
    found_i = found_j = True

    while True:
        if found_i and found_j:
            yield (next_i, next_j)
        elif not found_i and not found_j:
            break  # Both sequences empty

        if found_i: 
            for jj in earlier_values_j:
                yield (next_i, jj)
        if found_j:
            for ii in earlier_values_i:
                yield (ii, next_j)

        if found_i:
            earlier_values_i.append(next_i)
        if found_j:
            earlier_values_j.append(next_j)

        try:
            next_i = next(i)
            found_i = True
        except StopIteration:
            found_i = False

        try:
            next_j = next(j)
            found_j = True
        except StopIteration:
            found_j = False

在我脑海中这个问题很简单，但是在打出来之后看起来非常复杂，一定有更简单的方法。但我认为它会起作用。

- RemcoGerlich

Answer 4

你可以简单地使用生成器表达式：

from itertools import *
i = count(1)
j = count(1)

for e in ((x, y) for x in i for y in j):
    yield r

或者在Python3中：

yield from ((x, y) for x in i for y in j)

- Netwave

---

这不会增加 x 的值，因此即使给予无限时间，也不会生成所有的组合。 - muddyfish

@muddyfish，问题中没有指定这种行为，你真正想要实现什么？ - Netwave

修改后的问题，这样更好吗？ - muddyfish