python - 两个列表中项差的最小和

Question

假设我有两个像这样的 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 是更大的列表没有限制。
• 列表将按顺序排列
• 较短列表中的所有元素必须至少使用一次

Answer 1

为了确保得到正确的答案，我会使用二分加权匹配，其中每对之间的 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