# Anyone knows an algorithm that finds minimum distance for all permutations?

Let $$A$$ and $$B$$ be two finite sets of the same size $$n$$. Let $$P(A),P(B)$$ be the set of all permutations of $$A,B$$ respectively. A distance function $$d(a,b)$$ is defined for any $$a\in P(A),b\in P(B)$$. We want to find $$\min \{d(a,b):a\in P(A), b\in P(B)\}$$ (note: $$d$$ is fixed).

For example, suppose we have two sets $$\{1,2\}$$ and $$\{3,4\}$$, and the distance $$d$$ is Euclidean distance, then all possible distance values are

$$d((1,2),(3,4)) = \sqrt8$$

$$d((1,2),(4,3))=\sqrt {10}$$

$$d((2,1),(3,4)) = \sqrt{10}$$

$$d((2,1),(4,3)) = \sqrt{8}$$

So the minimum value is $$\sqrt 8$$.

I think this is a very common problem so there should be some known algorithm out there. Anyone knows an efficient algorithm to solve this problem and help provide the name or reference? Thank you!

• If $d$ can be arbitrary, there is little hope. You have to try all $n!^2$ pairs of permutations. Oct 17, 2016 at 21:40
• The answer will depend on what distance function $d$ you define for $a \in A, b \in B$. Is $d$ fixed? If so, what $d$ are you using? If it's not fixed but is part of the input to the algorithm, how is it specified? If $d$ is Euclidean distance, look at en.wikipedia.org/wiki/Nearest_neighbor_search, including en.wikipedia.org/wiki/…
– D.W.
Oct 17, 2016 at 21:50
• If $d$ is the Manhattan distance, or $L_1$, it looks like optimal matching to me. Oct 17, 2016 at 23:17
• "I think this is a very common problem": never heard of that. May 20 at 12:50

Surprisingly, if the distance is $L_p$, or the $p$-norm induced metric, then you simply sort $A$ and $B$ respectively, and then compute their distance, and that distance will be guaranteed minimal over all permutations. That is time complexity of $O(n\log n)$ and I believe it is the most efficient one.

Sometimes, before setting out to find an "efficient" algorithm, it might be a good practice to first think of proving the "greedy" algorithm is not right; because if the greedy indeed works, all efforts to search for the "efficient" algorithm will be in vain.

• Very nice. Having proposed a general approach, I didn't think if there is a simpler one for Lp metric. Oct 31, 2016 at 3:01
• What should I do if the values in the set are not 1 dimensional? Sorting and then compute their distance doesn't seem to work. Sep 11, 2019 at 22:51

If your weight function is just sum of pairwise distances between elements (or a monotone function of it) than this problem is reduced to the assignment problem. Most reasonable metrics (including $L_p$ for all $p$, which, in case, include Euclidean metric) satisfy this constraint. If so, we are only interested which pairs of elements are matched.

Let $a_{ij}$ be the cost of matching between $i$-th element of the first set and $j$-th element of the second set. Having the matrix $A$, you need select $n$ elements in it such that each column and each contain exactly one element and the sum of corresponding $a_{ij}$.

This is a classical problem, called assignment problem, which is effectively solved in $O(n^3)$ with Hungarian algorithm.

As far as I know, there are faster solutions ($O(n^{2.5})$ maybe), but I'm not sure. You can search for the min-cost max-flow algorithms which solve more general task and probably are being researched wider.