假设我有两个像这样的 python 列表:
[30, 400, 500]
[55, 396, 478]
我想找到元素之间的最小(绝对值)差之和。在这种情况下很容易:(55-30) + (400-396) + (500-478) = 51
但是当列表没有相同数量的元素时，我将如何有效地执行此操作。例如:
Set 1:
list1 = [30, 400, 500]
list2 = [412, 489]
即使是
Set 2
list1 = [30, 400, 500]
list2 = [24, 563]
最后，
Set 3
list1 = [30, 50]
list2 = [20, 31, 90]
对于第 1 组，答案是 (412-400) + (500-489) = 23
对于第 2 组，答案是 (30-24) + (563-500) = 69
对于第 3 组，答案为 (30-20) + (50-31) =29
我无法按元素进行比较。在set 1中，最小差的和是通过比较list1的第二个元素和list2的第一个元素，以及list1的第三个元素和list2的第二个元素来实现的。在集合2中，最小差的和是通过比较list1的第一个元素和list2的第一个元素，以及list1的第三个元素和list2的第二个元素来实现的。
感谢任何帮助。
一些其他信息:
- 列表的长度永远不会超过另一个列表的 2 倍，但是对于 list1 是更大的列表还是 list2 是更大的列表没有限制。
- 列表将按顺序排列
- 较短列表中的所有元素必须至少使用一次
请您参考如下方法:
为了确保得到正确的答案，我会使用二分加权匹配，其中每对之间的 abs-diff 是权重。这将避免基于排序的方法的所有陷阱，例如
list1=[30, 50], list2=[20, 31, 90], ans= 29
大多数直观算法会将 30 与 31 配对。(给出总和 41)
这是一个使用 scipy 的 linear_sum_assignment 的解决方案:
import numpy as np
from scipy.optimize import linear_sum_assignment
def min_diff_sum(list1, list2):
arr1 = np.asanyarray(list1)
arr2 = np.asanyarray(list2)
cost_matrix = np.abs(arr1-arr2[:, None])
pairs = linear_sum_assignment(cost_matrix)
return np.sum(cost_matrix[pairs])
这应该总是给出正确的结果。
In [45]: min_diff_sum([30, 400, 500], [412, 489])
Out[45]: 23
In [46]: min_diff_sum([30, 400, 500], [24, 563])
Out[46]: 69
