重新排序列表以使相邻元素的差值总和最小

Question

假设我们有一个列表。我们怎么能重新排列这个列表，使得相邻两个元素之间的总差值尽可能小呢？

比如说，列表是 [7, 4, 2, 6]。相邻两个元素之间的差值分别是 3、2 和 4，所以总差值是 9。

我们可以把它重新排列成 [2, 4, 6, 7]（这不是简单的排序）。这样，相邻两个元素之间的差值就变成了 2、2 和 1，总差值变成了 5。

我已经写了一个函数来计算列表的总差值。

def total_diff(test_list):
    t = 0
    for i in range(1, len(test_list)):
        t += test_list[i] - test_list[i-1]
    return t

接下来我应该怎么做呢？

Answer 1

你的 total_diff 函数需要计算差值的 绝对值 的总和：

def total_diff(test_list):
    t = 0
    for i in range(1, len(test_list)):
        t += abs(test_list[i] - test_list[i-1])
    return t

否则，这些差值会形成一个叫做 望远镜级数 的东西，它的总和只和列表的第一个和最后一个元素有关。

TD(L) = (L[1] - L[0]) + (L[2] - L[1]) + (L[3] - L[2]) + ... + (L[n-1] - L[n-2])
      = -L[0] + (L[1] - L[1]) + (L[2] - L[2]) + ... + (L[n-1] - L[n-2])
      = -L[0] + L[n-1]