如何高效排序等长列表使元素配对平方差和最小？（含多项式根追踪场景）

需求说明 #

给定两个等长列表：

l1 = [2.5, 1.1, 3.6]
l2 = [3.4, 1.0, 2.2]

需要对l2进行排序，得到l2_sorted = [2.2, 1.0, 3.4]，使得求和式Σ(l2_sorted[i] - l1[i])²取最小值。

背景场景 #

多项式x³ + a x² + b x + c = 0的三个复根root_A、root_B、root_C会随参数a、b、c在复平面连续变化，需要追踪每个根的对应关系。仅按位置排序无效，因为根的轨迹会交叉；而实际问题常涉及高次多项式，根的数量多，手动追踪完全不现实。

核心思路 #

这个问题本质是指派问题（Assignment Problem）：要在两个集合的元素之间找到一一对应的匹配，使得总代价（此处为平方差之和）最小。

• 小规模场景（根数量少，比如n≤10）：可以暴力枚举l2的所有排列，计算每个排列的总平方和，取最小值对应的结果。
• 大规模场景（高次多项式，根数量多）：必须用匈牙利算法（Hungarian Algorithm），它能以O(n³)的时间复杂度解决指派问题，效率远高于暴力枚举。

实操代码 #

小规模场景：暴力枚举

import itertools

l1 = [2.5, 1.1, 3.6]
l2 = [3.4, 1.0, 2.2]

min_total = float('inf')
best_permutation = None

# 枚举l2的所有排列
for perm in itertools.permutations(l2):
    current_total = sum((p - l1[i])**2 for i, p in enumerate(perm))
    if current_total < min_total:
        min_total = current_total
        best_permutation = perm

print(f"最优排序结果：{list(best_permutation)}")
print(f"最小平方和：{min_total}")

运行结果：

最优排序结果：[2.2, 1.0, 3.4]
最小平方和：0.86

大规模场景：匈牙利算法

借助scipy库实现高效计算：

from scipy.optimize import linear_sum_assignment
import numpy as np

l1 = [2.5, 1.1, 3.6]
l2 = [3.4, 1.0, 2.2]

# 构建代价矩阵：每个元素对应l1[i]和l2[j]的平方差
cost_matrix = np.array([[(x - y)**2 for y in l2] for x in l1])

# 用匈牙利算法找到最优匹配的索引
row_indices, col_indices = linear_sum_assignment(cost_matrix)

# 根据匹配索引生成排序后的l2
l2_sorted = [l2[i] for i in col_indices]

print(f"最优排序结果：{l2_sorted}")
print(f"最小平方和：{cost_matrix[row_indices, col_indices].sum()}")

运行结果和暴力枚举一致，且能轻松处理几十甚至上百个根的场景。

复根场景适配 #

如果是复根追踪，只需把代价改为复平面上的欧几里得距离平方（即|z1 - z2|²），其余逻辑不变：

# 示例：假设l1和l2是复根列表
l1 = [2+3j, 1-2j, 4+1j]
l2 = [1+2j, 3+4j, 0-1j]

# 构建复根的代价矩阵
cost_matrix = np.array([[abs(z1 - z2)**2 for z2 in l2] for z1 in l1])

row_indices, col_indices = linear_sum_assignment(cost_matrix)
l2_sorted = [l2[i] for i in col_indices]

这样就能正确追踪复根的对应关系，避免轨迹交叉导致的匹配错误。

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