如何重排列表使连续元素总差值最小？已实现差值计算函数

核心思路 #

要让连续元素的总差值尽可能小，最优方案是把列表按升序（或降序）排列。因为排序后相邻元素都是数值最接近的，它们的差值累加总和就是所有可能排列里的最小值。

具体操作步骤 #

• 第一步：对原列表进行排序。可以用Python内置的sorted()函数，默认是升序排序，也可通过reverse=True参数实现降序，两种排序方式的总差值结果一致。
• 第二步：用你已实现的total_diff()函数计算排序后列表的总差值，验证结果。

代码示例 #

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

# 原列表
original_list = [7, 4, 2, 6]
# 升序排序
sorted_list = sorted(original_list)
# 计算最小总差值
min_total_diff = total_diff(sorted_list)

print(f"排序后的列表：{sorted_list}")
print(f"最小总差值：{min_total_diff}")

为什么排序是最优解？ #

假设存在非排序的排列总差值更小，那必然存在至少一对相邻元素的差值大于排序后对应位置的差值。但排序后所有相邻元素的差值都是当前最小的可能，累加起来的总和不可能被其他排列超越。比如原列表[7,4,2,6]，排序后相邻差值为2、2、1，总和5；原排列差值为3、2、4，总和9，显然排序结果更优。

内容的提问来源于stack exchange，提问作者explosivebazooka