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!