两个列表中项差的最小和

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

解决这个问题的一种方法是先选择较小的列表。从较小的列表中一个一个地取出数字并搜索最小绝对差（同时跟踪索引），一旦找到最小绝对差，将其添加到最终的 sum 并从较大的列表中删除该元素，以便您不会再考虑了。

这个解决方案是 O(NM)。假设 list1 和 list2 的列表大小约束分别为 N、M。您可以通过对 O(NLogN) 中较大的列表进行排序并使用二进制搜索找到最小绝对差来优化 O(NLogN + NLogM) 的解决方案。

Answer 2

您可以使用 bisect 模块：

import bisect

list1 = [30, 400, 500]
list2 = [412, 489]


list1.sort() # list1 must be sorted

result = []

for el in sorted(list2): # walk through the elements in sorted order
    pos = bisect.bisect_left(list1, el) # find the closest elements
    if pos >= len(list1): # el is bigger than last element, use it
        pos -= 1
    elif pos > 0 and abs(list1[pos-1] - el) <= abs(list1[pos] - el):
        pos = pos - 1
    result.append(abs(list1[pos] - el))
    del list1[pos]

print(result)

结果为 [12, 11]（即 [412-400, 500-489]）

如果你使用 list2 = [24, 563] 那么你会得到 [6, 63]（即 [30-24, 563-500]）

Answer 3

如果我理解正确，我相信以下内容应该有效：

list1 = [30, 400, 500]
list2 = [412, 489]

diffs = []
pairs = []
for l2 in list2:
    min_diff = float('inf')
    pair     = None
    for l1 in list1:
        abs_diff = abs(l2-l1)
        if abs_diff < min_diff:
            min_diff = abs_diff
            pair = (l1,l2)
    diffs.append(min_diff)
    pairs.append(pair)

print(diffs)
print(sum(diffs))
print(pairs)

在评论中指出了错误，这里是修改后的版本。

import itertools
def min_abs_diff(l1,l2):
    bigger, smaller = sorted([l1,l2],key=len,reverse=True)
    diffs = [abs(x-y) for x,y in itertools.product(bigger,smaller)]
    return sum(min(diffs[i*len(bigger):(i+1)*len(bigger)]) 
               for i in range(len(diffs)//len(bigger)))

Answer 4

使用排序和压缩。

>>> list1 = [30, 400, 500]
>>> list2 = [412, 489]
>>> l3 = zip(sorted(list1), sorted(list2))
>>> s = 0
>>> for i in l3:
...   s += abs(i[0] - i[1])
...
>>> s
23

如果您仍然需要使用列表中的 "hanging" 值，您可以使用 zip_longest 和 fillvalue 作为默认值来配对悬挂值。然后使用排序，您可以添加 reverse=True 将列表更改为降序。

编辑

有了添加的信息，删除 reverse=True 就差不多了。

Answer 5

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

Answer 6

好的，在开始编码之前，这就是我对问题的推理方式： 1. 简单计算所有可能的值。 2.只取出最小的我不认为任何更复杂的东西都会更有效率，因为最终，您仍然必须测试所有组合以获得完全的确定性。考虑到这一点，我会这样做：

ll1, ll2 = len(l1), len(l2) 
if ll2 < ll1:
    l1, l2, ll1, ll2 = l2, l1, ll2, ll1
# Now any longer list will be l2 and ll2 >= ll1

在这个阶段，我们需要一个能够将单个列表拆分为列表列表的函数，其中每个子列表（即项目）的长度由指定的数字给出。它们也不能包含相同的项目（来自拆分列表）两次。输入 itertools。

from itertools import combinations, permutations 
# All the lists within l2 that will be mixed with l1 (that is they have same length as l1) :
l2_sublists = combinations(l2, ll1) 
mixes = [l1 + item for item in l2_sublists]

为了得到每个组合的所有差异总和，我们找到了所有组合；将它们分成两部分；然后对于每个组合求和每个分区中项目差异的绝对值...

diffs = (sum(abs(p[0] - p[1]) for p in (perm[i:i + 2] for i in range(0, len(perm), 2))) for m in mixes for perm in permutations(m, 2 * ll1)) 
result = min(diffs) 
print(result)

两个列表中项差的最小和

Minimum summation of difference of terms in two lists

python

comparison

list

difference