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

Question

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

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

对于ls1中的每个元素，我们必须将其与ls2中的一个元素配对，使得ls1中的元素与ls2中的元素之间的（绝对值）差的总和最小。每个元素只能匹配一次。在上面的例子中，最优的方式是将ls1中的4与ls2中的3匹配，将ls1中的5与ls2中的6匹配，这样可以得到总差：

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

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

我知道使用排列来暴力解决问题是一种选择，但我需要一个具有最佳时间和空间复杂度的代码。我听说过动态规划的概念，但我不知道如何在我的情况下实现它。提前感谢回复。

附带我的当前暴力代码，它使用排列，但运行时效率和内存使用效率都不高：

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

- Jingjie Yang

---

这看起来像是作业，你能展示一下你尝试过什么吗？如果这确实是作业，请在你的问题中注明。 - TemporalWolf

另外，您想要每个列表的n索引之间的最小差异或整体上的最小差异，即两个列表中任意元素之间的差异？ - Moinuddin Quadri

实际上，您只是在寻找不共享运算数的两个最小绝对差。 - Patrick Haugh

@AdamSmith 只是abs(4 - 3) + abs(6 - 5)，在这种情况下没有什么区别，但在其他情况下有区别。 - Jingjie Yang

@AdamSmith老实说，那是我在尝试排列之前最初的想法。 - Jingjie Yang

Answer 1

可以证明，最优解是将两个列表排序，并按排序顺序匹配它们的元素。

证明概述： 1. 假设存在一个反转，即 a 匹配到 b，c匹配到d，且a < c，b > d。 2. 我们可以“交换”这些元素：a->d, c->b。现在a < c，d < b。可以证明，该操作从不增加答案（通过考虑a、b、c、d的所有可能相对值）。 3. 因此，总是有一个最优匹配，其中两个列表都被排序。

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

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

- kraskevich

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。

为了实现这一点，我们只需将一个列表中的最大值乘以另一个列表中的最大值，然后对于两个列表中的第二大值等做同样的操作（参见给定两个数组，找到索引乘积的最小和）。因此，通过对两个列表进行排序并将排序后列表中相同索引的元素相乘，我们可以获得差异的最小总和。

- Jingjie Yang