给定两个数组，找到给出两个数组之间最接近距离的排列

假设我有两个长度相同的数组n, named A and B.

这两个数组包含实数值。 我们将两个数组之间的距离定义为均方距离。

dist(A,B) = sqrt( sum((A - B)2) )

我想找到的排列A这给出了最小距离B。 最简单的方法是尝试每一个排列A并记录最小距离。然而，该方法的复杂度为 O(n!)。

有没有复杂度小于 O(n!) 的算法？

您可以对 A 和 B 进行排序。在这种情况下，欧几里得距离是最小的。

如果 B 必须保持固定，那么您只需反转对 B 进行排序所需的排列并将其应用于 A 的排序版本。

该解决方案确实假设您只想找到一个排列，而不是最简单的排列（因为通过排列进行排序和取消排序不会非常有效）。

Proof:让 S,T 成为我们的数组对。 不失一般性，我们可以假设 S 已排序，因为所有这些 重要的是两组元素之间的映射。

令 T 为最小化两个数组之间距离的排列， 设 d 为该距离。

假设 T 是not已排序。那么存在元素 i,j s.t. T_i > T_j

S_i + k1 = S_j
T_i = T_j + k2
where k1,k2 > 0

令 x 为除 i 和 j 之外的所有元素的总距离。

d = x + (S_i - T_i)^2 + ((S_i + k1) - (T_i - k2))^2

如果我们交换 T_i 和 T_j 的顺序，那么我们的新距离是：

d' = x + (S_i - (T_i - k2))^2 + ((S_i + k1) - T_i)^2

因此： d - d' = 2 * k1 * k2，这与我们的假设相矛盾，即 T 是最小化距离的排列，因此必须对这样做的排列进行排序。

使用多种方法可以在 O(n log n) 内完成对两个数组的排序。