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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|improve this answer
Thank you. As I suspected, I simply did not know the name of what I was looking for. 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.

share|cite|improve this answer

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:

share|cite|improve this answer

Your Answer


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.