Ykhjuy

Lets 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 array as the mean squared distance.

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

I wan 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!)?

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.

Would it be a possibility to just sort both A and B? In that case I would assume the Euclidean distance to be minimal. I think this approach is mathematically sound, but I haven't proved it properly.

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).

Construct a bipartite graph from the vectors. Find minimum weight perfect matching in this graph.

How to construct the graph.

1. Let A, B be two parts of the graph. Each with n nodes.


2. Connect i in A to j in B with an edge of weight abs(A[i] - B[j]).

I believe this can be done in O(n^2).

See http://www.cse.iitd.ernet.in/~naveen/courses/CSL851/lec4.pdf

If each number in A has only one closest number in B then you can do this in O(n log n). This probably might be the case since you have the real numbers.

How?

1. Sort A O(n log n)


2. Binary search for the closest number for each number in B. O(n log n).

If the numbers are coming from the real world and have even a little bit of randomness to them, then the differences between each pair of the numbers is probably unique. You can verify if this is the case by running experiments on the input vectors. Then the problem becomes easy to solve yay!