從列表中獲取對的最快方法

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" 

Answer 2

在距離外環將工作：

((a, a + d) for d in range(1, n) for a in range(n - d))