时间戳

首页 > 解决方案 > 两个列表中术语差异的最小总和

python - 两个列表中术语差异的最小总和

问题描述

假设我有两个这样的 python 列表：

[30、400、500]

[55、396、478]

我想找到元素之间的最小（绝对值）差异的总和。在这种情况下，这很容易：(55-30) + (400-396) + (500-478) = 51

但是当列表没有相同数量的元素时，我将如何有效地做到这一点。例如：

设置 1：

list1 = [30, 400, 500]

列表 2 = [412, 489]

或者即使是

设置 2

list1 = [30, 400, 500]

列表 2 = [24, 563]

最后，

设置 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

我无法按元素进行比较。在集合 1 中，通过将 list1 的第二个元素与 list2 的第一个元素进行比较，将 list1 的第三个元素与 list2 的第二个元素进行比较，得到最小差之和。在集合 2 中，通过将 list1 的第一个元素与 list2 的第一个元素进行比较，将 list1 的第三个元素与 list2 的第二个元素进行比较，得到最小差之和。

任何帮助表示赞赏。

其他一些信息：

标签： pythonlistcomparisondifference

解决方案

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

推荐阅读