You can just sort both A and B. In that case, the Euclidean distance is minimal.
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).
Proof:
Let S,T be our pair of arrays.
We can assume S to be sorted without loss of generality, since all that
matters is the mapping between the two sets of elements.
Let T be the permutation that minimizes the distance between the two arrays,
and let d be that distance.
Suppose that T is not sorted. Then there exist elements i,j s.t. T_i > T_j
S_i + k1 = S_j
T_i = T_j + k2
where k1,k2 > 0
Let x be the total distance of all elements except i and j.
d = x + (S_i - T_i)^2 + ((S_i + k1) - (T_i - k2))^2
If we swap the order of T_i and T_j, then our new distance is:
d' = x + (S_i - (T_i - k2))^2 + ((S_i + k1) - T_i)^2
Thus:
d – d’ = 2 * k1 * k2, which contradicts our assumption that T is the permutation that minimizes the distance, so the permutation that does so must be sorted.
Sorting the two arrays can be done in O(n log n) using a variety of methods.