Given two $nPn$ permutations of the same $n$-sized set, how can one find out the similarity between these permutations over the interval $[0, 1]$?
Similarity between two nPn permutations of the same set.
1
$\begingroup$
permutations
-
0If you have two permutations $\sigma_1$ and $\sigma_2$, you can find the "difference" between them as the permutation $\sigma_2\sigma_1^{-1}$, of which you can compute the inversion number or the disorder (same thing) as shown by the two existing answers. – 2012-08-20
2 Answers
2
The "Inversion number" is a common way of measure permutation distance. There are other mesasures, (edit measures, as Levenshtein distance) that are actually more general (they measure arbitrary "strings" distance), but can be applied to permutations as special cases.
1
See the section on computing the "disorder" of a permutation in these notes by Chris Cooper. It's Section 12.