无限生成器的Python产品 [英] Python product of infinite generators
问题描述
我正在尝试获取2个无限生成器的乘积，但itertools中的product函数 doesn 这种行为.
I'm trying to get the product of 2 infinite generators but the product function in itertools doesn't allow this sort of behaviour.
示例行为:
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) ...)
只要给定无限时间，返回组合的顺序并不重要，最终将生成所有组合.这意味着在给定元素组合的情况下，使用该组合返回的生成器中必须有一个有限索引.
It doesn't matter in which order the combinations get returned as long as given infinite time, all combinations will be eventually generated. This means that given a combination of elements, there must be a finite index in the returned generator with that combination.
推荐答案
tl; dr
下面提供的代码现已包含在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
惰性解决方案
如果您不关心顺序，因为生成器是无限的，那么有效的输出将是:
The lazy solution
If you don't care about order, since the generators are infinite, a valid output would be:
(a0, b1), (a0, b2), (a0, b3), ... (a0, bn), ...
因此，您可以仅从第一个生成器中获取第一个元素，然后在第二个生成器上循环.
So you can just take the first element from the first generator and then loop over the second.
如果您确实想执行此操作，则需要一个嵌套循环，并且需要用tee复制该嵌套生成器，否则您将无法再次遍历它(即使它没关系，因为您将永远不会耗尽发电机，因此您将不需要循环)..
If you really want to do it, you need a nested loop, and you need to duplicate the nested generator with tee, otherwise you will not be able to loop over it a second time (even if it doesn't matter because you will never exhaust the generator, so you will never need to loop over).
但是，如果您真的很想做，这里就可以了:
But if you really really really want to do it, here you have it:
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的单个副本.首先尝试使用有限生成器.
The idea is to always make a single copy of gen2. Try it with finite generators first.
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扫描算法.
The zig-zag algorithm
As noted by others in comments (and as stated in the previous solution), this will not produce all the combinations. Nevertheless the mapping between natural numbers and pairs of numbers exists, so it must be possible to iterate the pairs in a different way, so that looking for a specific pair (without infinite numbers) can be done in finite time, you need the zig-zag scanning algorithm.
为此，您需要缓存以前的值，因此我创建了一个类GenCacher来缓存以前提取的值:
In order to do it you need to cache previous values, so I created a class GenCacher to cache previously extracted values:
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算法:
After that you just need to implement the zig-zag algorithm:
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
将解决方案扩展到2个以上的发电机
我们可以对解决方案进行一些编辑，以使其甚至可以用于多个生成器.基本思想是:
Extend the solution to more than 2 generators
We can edit the solution a bit to make it work even for multiple generators. The basic idea is:
-
在距
(0,0)的距离(索引的总和)上迭代.(0,0)是距离为0的唯一一个，(1,0)和(0,1)的距离为1，依此类推.
iterate over the distance from
(0,0)(the sum of the indexes).(0,0)is the only one with distance 0,(1,0)and(0,1)are at distance 1, etc.
生成该距离的所有索引元组
generate all the tuples of indexes for that distance
提取相应的元素
我们仍然需要GenCacher类，但是代码变为:
We still need the GenCacher class, but the code becomes:
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))
这篇关于无限生成器的Python产品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
