Given two arrays, find the permutations that give closest distance between two arrays

Let's say I have two arrays of the same length n, named A and B.

These two arrays contain real values. We define the distance between two arrays as the mean squared distance.

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

I want to find the permutation of A that gives the min distance to B. The naive method is to try every permutation of A and record the min distance. However, this method is of complexity O(n!).

Is there an algorithm of complexity less than O(n!)?

Solution 1:

You can just sort both A and B. In that case, the Euclidean distance is minimal.

If B has to remain fixed, then you just need to invert the permutation needed to sort B and apply that to the sorted version of A.

This solution does assume that you want to find just a permutation and not the most simple permutation (since sorting and unsorting through permutations will not be incredibly efficient).

Proof: Let S,T be our pair of arrays. We can assume S to be sorted without loss of generality, since all that matters is the mapping between the two sets of elements.

Let T be the permutation that minimizes the distance between the two arrays, and let d be that distance.

Suppose that T is not sorted. Then there exist elements i,j s.t. T_i > T_j

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

Let x be the total distance of all elements except i and j.

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

If we swap the order of T_i and T_j, then our new distance is:

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

Thus: d - d' = 2 * k1 * k2, which contradicts our assumption that T is the permutation that minimizes the distance, so the permutation that does so must be sorted.

Sorting the two arrays can be done in O(n log n) using a variety of methods.

Solution 2:

The problem you describe is equivalent to the Minimum Cost Perfect Matching Problem which can be solved efficiently (and exactly) using The Hungarian Algorithm. In the Minimum Cost Perfect Matching Problem you have an input weighted bipartite graph where the two sets have the same size n, and each edge has a non-negative cost. The goal is to find a perfect matching of minimum cost.

In your case, the bipartite graph is a biclique. That is, every vertex in one set is connected to every vertex in the other set, and the cost of edge (i,j) is (A[i] - B[i])^2 (where i corresponds to index i in array A and j corresponds to index j in array B).

EDIT: This is not the best solution for the problem. Ivo Merchiers came up with a better solution both in terms of efficiency and simplicity. The reason I'm not deleting my answer is because my suggested solution is valuable for distance measures to which Ivo's solution does not apply (as his approach works by exploiting a property of the Euclidean distance).