两个列表中元素之间的最小差和

Question

假设我们有两个长度相同的列表，ls1 和 ls2。例如，我们有

ls1 = [4, 6]
ls2 = [3, 5]

并且对于 ls1 中的每个元素，我们必须将它与 ls2 中的一个元素和一个元素配对，其方式使得总（absolute) ls1 中的元素与 ls2 中的元素之间的差异很小。一个元素只能匹配一次。在上面的例子中，最佳的匹配方式是 4 是 ls1 与 ls2 中的 3，以及 ls1 中的 5 与 [= ls2 中的 25=]，总差为

(4 - 3) + (6 - 5) = 2

我需要一个程序来 return 这两个列表中元素之间的最小总差。列表的长度是任意的，列表中元素的值也是任意的（但它们都是正整数）。

我目前知道使用排列来暴力破解解决方案是一种选择，但我需要的是具有最佳时间和 space 复杂性的代码。我听说过动态规划的概念，但我不知道如何在我的案例中实施它。预先感谢您的回复。

Ps。这是我当前使用排列的蛮力代码，它在运行时或内存使用方面效率不高：

from itertools import permutations

def minimum_total_difference(ls1, ls2):
    length = len(ls1)
    possibilities = list(permuations(ls1, length))
    out = 10**10
    for possibility in possibilities:
        out_ = 0
        for _ in range(length):
            diff = abs(possibility[_] - ls2[_])
            out += diff
        if out_ < out:
            out = out_
    return out

Answer 1

可以证明最佳解决方案是对两个列表进行排序并按排序顺序匹配它们的元素。

证明草图：

设一个倒置，即a匹配b，c匹配d，a < c, b > d.
我们可以"exchange"这些元素：a->d, c->b。现在a < c, d < b。可以证明这一操作永远不会增加答案（通过考虑 a, b, c, d 的所有可能的相对值）
因此，在两个列表都排序的情况下，总有一个最佳匹配。

这是实现此解决方案的高效单行代码：

sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys)))

Answer 2

正如@kraskevich 所指出的，正确答案确实是：

sum(abs(x - y) for x, y in zip(sorted(xs), sorted(ys))

我已经给出了自己的证明：
考虑两个列表 xs 和 ys 由元素组成，按随机顺序 x1，x2，... xn 和 y1，y2, ... yn.
由于我们要求绝对差之和的最小值，所以可以用平方根代替绝对值，这样对求最小值影响不大。
因此，差异之和为：

(x1 - y1)^2 + (x2 - y2)^2 + ... + (xn - yn)^2 
=x1^2 - 2x1 * y1 + y1^2 + ... + xn^2 - 2xn * yn + yn^2

正如我们所见，无论我们以何种方式排列这两个列表，二次项 xn^2 和 yn^2 都保持不变。所以，为了获得最小的结果，我们只需要最大化负项 -2xn * yn.

为此，我们只需将一个列表中的最大值乘以另一个列表中的最大值，然后对两个列表中的第二大值执行相同操作，依此类推（参见 ).因此，通过对两个列表进行排序并将排序列表中相同索引的元素相乘，我们获得了最小的差异和。

两个列表中元素之间的最小差和

Smallest sum of difference between elements in two lists

python

algorithm

np