如何迭代笛卡尔积,使顶级项首先组合? [英] How to iterate the cartesian product so top items combine first?
问题描述
我需要获得可迭代的笛卡尔积,比如 itertools.product
给我,但出于优化原因,我希望那些具有最低索引总和的对/组合首先出现。
I need to get the cartesian product of iterables, like itertools.product
gives me, but for optimization reasons I want those pairs/combinations with the lowest sum of indices to appear first.
因此,例如,如果我有两个列表, a = [1,2,3,4,5]
和 b = ['a','b','c','d','e']
, itertools .product
给了我:
So, for example, if I have two lists, a = [1, 2, 3, 4, 5]
and b = ['a', 'b', 'c', 'd', 'e']
, itertools.product
gives me:
>>> list(itertools.product(a, b))
[(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'), (1, 'e'), (2, 'a'), (2, 'b'), (2, 'c'), (2, 'd'), (2, 'e'), (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd'), (3, 'e'), (4, 'a'), (4, 'b'), (4, 'c'), (4, 'd'), (4, 'e'), (5, 'a'), (5, 'b'), (5, 'c'), (5, 'd'), (5, 'e')]
相反,我想要在(1,'c')
之前看(2,'a')
。确切的顺序,例如, (1,'b')
和(2,'a')
,并不重要。
Instead, I would want to see (2, 'a')
before (1, 'c')
. The exact order, between e.g. (1, 'b')
and (2, 'a')
, is unimportant.
目前,我正在根据指数范围的乘积对列表进行排序:
Currently, I am sorting a list based on the product of the index ranges:
>>> sorted(list(itertools.product(range(len(a)), range(len(b)))), lambda a, b: sum(a) - sum(b))
[(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), (0, 4), (1, 3), (2, 2), (3, 1), (4, 0), (1, 4), (2, 3), (3, 2), (4, 1), (2, 4), (3, 3), (4, 2), (3, 4), (4, 3), (4, 4)]
然后用它来索引列表。但是,长列表会占用太多内存。我需要某种具有与 itertools.product
相同的调用约定的生成器,但是我无法弄清楚迭代的方式以便我得到排序和所有可能的对一次。
Then using that to index the lists. However, this takes too much memory with long lists. I need some kind of generator with the same calling convention as itertools.product
, but I cannot figure out the way to iterate so that I get both the ordering and all the possible pairs exactly once.
推荐答案
def cartprod(x,y):
nx = len(x)
ny = len(y)
for i in range(nx+ny):
for j in range(max(0,i-ny+1), min(i+1,nx)):
yield (x[j],y[i-j])
这篇关于如何迭代笛卡尔积,使顶级项首先组合?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!