# Fast algorithm for Spearman footrule distance between two permutations?

Given a set $S$ and two permutations of $S$, $\sigma$ and $\pi$, such that $\sigma(i)$ gives the rank of $i$ according to permutation $\sigma$ and $\pi(i)$ gives the rank of $i$ according to permutation $\pi$ ($i \in S$).

The distance between $\sigma$ and $\pi$ according to the subject metric is $$\sum_{\forall i \in S} |\sigma(i) - \pi(i)|$$

And a ''naive'' pseudo-code is

// a, b: permutation arrays (same size and elements, but order may differ)
int dist(int[] a, int[] b) {
D = 0
for (i=0; i<a.Length; i++) {
pos = find the position of a[i] in b
D = D + |pos-i|
}
return D
}


This implementation works pretty well for small size permutations, but I need to run it against permutations of huge size unfortunately.

So, is there a better (faster) version of this algorithm?

The "rank" vectors $\sigma$ and $\pi$ are the inverses of the permutations a and b respectively. So it's faster to compute $\sigma$ with a single pass over a, compute $\pi$ with a pass over b, then computing the footrule is a linear pass over $\sigma$ and $\pi$, so this is linear time and space overall.
• In theory, I guess you're right. But AFAIK the only way to compute $\sigma$ and $\pi$ in $O(1)$ time is by using hashing table data structures, which are subject to inaccuracy due to their collision-ability nature. Without hashing tables, we can use $O( \log n)$ binary search, which results in $O(n \cdot \log n)$, which is much better than the $O(n^2)$ algorithm in my question. – user215750 Oct 3 '15 at 1:50