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

  • A+
Category:Languages

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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: