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