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.

I've found this a frustrating topic to Google, and might have an entire field dedicated to it that I'm unaware of.

Given an permutation of consecutive integers, I would like a "score" (real [0:1]) that evaluates how in-order it is.

Clearly I could count the number of misplaced integers wrt the ordered array, or I could do a "merge sort" count of the number of swaps required to achieve order and normalise to the length of the array. Has this problem been considered before (I assume it has), and is there a summary of the advantages of various methods?

I also assume there is no "true" answer, but am interested in the possibilities.

share|improve this question
1  
I imagine it would depend on what you would expect of the "measure". The only sensible one that I'm aware of is the number of inversions. –  tomasz Sep 25 '12 at 19:35
    
Yes I apologise for the vagueness of my requirements, I suppose I'm looking for any other method to consider apart from the two I've given. For instance some kind of fourier/discrete transform may give an appropriate response, although I haven't looked into it. –  Dijkstra Sep 25 '12 at 19:40
add comment

3 Answers

up vote 3 down vote accepted

The most famous are inversion distance to the sorted list and the sum of distances that the elements have moved. In statistics these are called Kendall's $\tau$ and Spearman's footrule.

Search for "distance metric on symmetric group"

Search for "distance metric on S_n"

Search for "distance between rankings"

Blog entry from Peter Cameron

share|improve this answer
    
Thank you. As I suspected, I simply did not know the name of what I was looking for. en.wikipedia.org/wiki/Rank_correlation gives a good overview. –  Dijkstra Sep 26 '12 at 14:19
add comment

You might want to try including "Symmetric group" in your Google searches, if you haven't already. The set of all permutations of the first $n$ integers is a particularly example of a symmetric group.

I found this reference, which is a survey of metrics defined on symmetric groups. You can convert any of these into a norm (what you're looking for) by defining the "score" of the permutation to be its "distance" from the trivial permutation ($123\dots n$) under the metric you choose. You can then scale that to be between $0$ and $1$ by just finding the permutation that is "furthest" from the trivial one, and making that have score 1.

share|improve this answer
add comment

One book which treats metrics on permutations (that is, metrics on the symmetric group) is Persi Diaconis:"Group representations in probability and statistics"

which it is possible to download from here: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.lnms/1215467407

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.