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

假设我有两个长度相同的数组n，分别命名为A和B。

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

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

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

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

标签： algorithm

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

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

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

证明： 令 S,T 为我们的数组对。我们可以假设 S 已排序而不失一般性，因为重要的是两组元素之间的映射。

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

假设 T没有排序。那么存在元素 i,j st 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) 中对两个数组进行排序。