Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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]$?

share|improve this question
    
Is your idea that the sequence $\langle A, B, C, D, E\rangle$ should be considered similar to $\langle B, A, C, D, E\rangle$ and to $\langle E, A, B, C, D\rangle$, but less similar to $\langle C, E, D, A, B\rangle$? –  MJD Jun 17 '12 at 16:26
    
Yes, exactly. But how to quantify it? I search on the Internet, and found that one can think in terms of counting the number of "shift" operations it would take to convert one permutation into the other--something similar to Hamming distance. –  user1030497 Jun 17 '12 at 16:33
    
If 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. –  Rahul Aug 20 '12 at 3:44
add comment

2 Answers

See the section on computing the "disorder" of a permutation in these notes by Chris Cooper. It's Section 12.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.