假设我有两个类似的python列表：
[300400500]
[55396478]
我想找到元素之间最小(的绝对值(差的和。在这种情况下，很容易：(55-30(+(400-396(+(500-478(=51
但是，当列表中的元素数量不相等时，我该如何有效地完成这项工作呢。例如：
集合1:
list1=[30040050]
list2=[412489]
或者即使是
设置2
list1=[30040050]
list2=[24563]
最后，
设置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的第一个元素进行比较，并将list 1的第三个元素与list 2的第二个子元素进行比较来获得最小差的和。在集合2中，通过将list1的第一元素与list2的第一元素进行比较，并将list1中的第三元素与list2中的第二元素进行比较来获得最小差的和。
感谢您的帮助。
其他一些信息：
- 列表的长度永远不会超过另一个列表的2倍，但list1是更大的列表还是list2是更大列表没有界限
- 列表将按排序
- 较短列表中的所有元素必须至少使用一次
为了确保得到正确的答案，我会使用二分加权匹配，其中每对之间的绝对差值是权重。这将避免基于排序的方法中的所有陷阱，例如
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
您可以使用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](
解决此问题的一种方法是先选择较小的列表。从较小的列表中一个接一个地取数字，搜索最小绝对差(也要跟踪索引(，一旦找到最小绝对差，就将其添加到您的最终sum中，并从较大的列表中删除该元素，这样您就不会再考虑了。
这个解是O(NM(。假设列表大小约束对于列表1和列表2分别为N、M。您可以通过在O(NLogN(中对较大的列表进行排序并使用二进制搜索来找到最小的绝对差异，来优化O(NLogN+NLogM(的解决方案。
好吧，在开始编码之前，我会这样解释这个问题：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)
使用排序和zip。
>>> 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
如果您仍然需要使用列表中的"挂起"值，则可以使用zip_lengest，其中fillvalue是默认值，以配对挂起值。然后通过排序，您可以添加reverse=True以将列表更改为降序。
编辑
有了添加的信息，删除reverse=True几乎就可以了
如果我正确理解了这一点，我相信以下内容应该有效：
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)))