python - 在 Python 中生成按总和排序的 (i,j) 序列

Question

我需要编写一个 Python 生成器来生成 range 中所有可能的数字对0..N。对必须按对的总和进行排序。是否可以高效地实现该 CPU？

序列示例：

(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2)

一个糟糕的实现，N=1000 需要 125 毫秒：

N = 1000
# t1 = time.time()
pairs = [(i, j) for i in range(N) for j in range(N)]
pairs2 = list(sorted(pairs, key=sum))
# t2 = time.time()
# print(f'took {t2 - t1} s, n={n}')
# print(pairs2)

首选生成器，因为在很多情况下迭代很快就会停止，所以我希望那时的时间消耗为零。

标签： pythongenerator

Answer 1

您可以将您的配对想象为 (x, y) 坐标。您想生成正方形中所有点的坐标。坐标和 ( ) 相等的点total位于向右下方的对角线上。

我们只需要遍历每个对角线上的所有点：

def pairs_by_sum(n):
    for total in range(0, n + 1):
        for x in range(0, total + 1):
            yield (x, total - x)
            
    for total in range(n+1, 2*n + 1):
        for x in range(total - n, n+1):
            yield(x, total - x)
            
print(list(pairs_by_sum(2)))
# [(0, 0),
#  (0, 1), (1, 0),
#  (0, 2), (1, 1), (2, 0), 
#  (1, 2), (2, 1),
#  (2, 2)]

print(list(pairs_by_sum(3)))
# [(0, 0), 
#  (0, 1), (1, 0), 
#  (0, 2), (1, 1), (2, 0),
#  (0, 3), (1, 2), (2, 1), (3, 0), 
#  (1, 3), (2, 2), (3, 1),
#  (2, 3), (3, 2),
#  (3, 3)]