如何迭代笛卡尔积,使顶级项目首先合并?
How to iterate the cartesian product so top items combine first?
我需要得到迭代器的笛卡尔积,就像 itertools.product
给我的一样,但出于优化原因,我希望那些 pairs/combinations 的索引总和最低的先出现。
因此,例如,如果我有两个列表,a = [1, 2, 3, 4, 5]
和 b = ['a', 'b', 'c', 'd', 'e']
,itertools.product
会给我:
>>> 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')
,并不重要。
目前,我正在根据索引范围的乘积对列表进行排序:
>>> 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
相同调用约定的生成器,但我无法找出迭代的方式,以便我同时获得排序和所有可能的对。
根据@otus 评论更新 - 生成按总和排序的索引,使用它们来查找值:
A = range(5)
B = 'abcde'
def indices(A,B):
# iterate all possible target sums in order
for m in range(max(A)+max(B)):
for a in A:
# stop once current target sum isn't possible
if a > m:
break
# yield if sum equals current target sum
if m-a in B:
yield a,m-a
def values(A,B):
for a,b in indices(range(len(A)),set(range(len(B)))):
yield A[a],B[b]
print list(values(A,B))
输出:
[(0, 'a'), (0, 'b'), (1, 'a'), (0, 'c'), (1, 'b'), (2, 'a'), (0, 'd'), (1, 'c'), (2, 'b'), (3, 'a'), (0, 'e'), (1, 'd'), (2, 'c'), (3, 'b'), (4, 'a'), (1, 'e'), (2, 'd'), (3, 'c'), (4, 'b'), (2, 'e'), (3, 'd'), (4, 'c'), (3, 'e'), (4, 'd')]
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])
我需要得到迭代器的笛卡尔积,就像 itertools.product
给我的一样,但出于优化原因,我希望那些 pairs/combinations 的索引总和最低的先出现。
因此,例如,如果我有两个列表,a = [1, 2, 3, 4, 5]
和 b = ['a', 'b', 'c', 'd', 'e']
,itertools.product
会给我:
>>> 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')
,并不重要。
目前,我正在根据索引范围的乘积对列表进行排序:
>>> 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
相同调用约定的生成器,但我无法找出迭代的方式,以便我同时获得排序和所有可能的对。
根据@otus 评论更新 - 生成按总和排序的索引,使用它们来查找值:
A = range(5)
B = 'abcde'
def indices(A,B):
# iterate all possible target sums in order
for m in range(max(A)+max(B)):
for a in A:
# stop once current target sum isn't possible
if a > m:
break
# yield if sum equals current target sum
if m-a in B:
yield a,m-a
def values(A,B):
for a,b in indices(range(len(A)),set(range(len(B)))):
yield A[a],B[b]
print list(values(A,B))
输出:
[(0, 'a'), (0, 'b'), (1, 'a'), (0, 'c'), (1, 'b'), (2, 'a'), (0, 'd'), (1, 'c'), (2, 'b'), (3, 'a'), (0, 'e'), (1, 'd'), (2, 'c'), (3, 'b'), (4, 'a'), (1, 'e'), (2, 'd'), (3, 'c'), (4, 'b'), (2, 'e'), (3, 'd'), (4, 'c'), (3, 'e'), (4, 'd')]
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])