# Measuring orderedness

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.

-
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

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

-
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

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.

-

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

-