python - 从列表中按距离排序的列表中获取对的最快方法

Question

给定一个 range(n)从列表中的每个元素的各自距离排序的范围中获取对的最快方法是什么，即对于列表中的两个元素 A和 B距离是abs(A-B) . 这是我想出的实现:

 sorted(combinations(range(n), 2), key=lambda a: -abs(a[0]-a[1]))

但我希望它成为一个更高效的发电机。

Answer 1

如果你想要一个生成器:

def distant_pairs(n):
    for d in range(n, 0, -1):
        for i in range(n-d):
            yield (i, i+d)

或者在散文中:对于每个可能的距离，从最大到最小，找到相距该距离的每一对并产生它。

这里有一个小的测试工具来展示它的工作原理:

for n in range(12):
    answer = list(distant_pairs(n))
    prev_answer = sorted(combinations(range(n), 2), key=lambda a: -abs(a[0]-a[1]))

    print "SIZE", n
    print answer
    print prev_answer
    assert answer == prev_answer
    print "---"
print "done"