0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user215750 Oct 3 '15 at 1:50
  • $\begingroup$ There's no inaccuracy in hash tables. Any decent hash table implementation works correctly even in the presence of collisions. (Or, use a balanced binary tree, if you don't understand hash tables.) So, the comment from @user215750 makes no sense to me. $\endgroup$ – D.W. Jun 2 '16 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy