metric for permutations?

Abstract Dissonance · science forum Guru Wannabe Joined: 29 Dec 2005 Posts: 201

Does anyone have any info on a way to measure the "distance" between two
permutations? I need a good method that will allow me to compare how "close"
one permutation is to another.

I could treat them as a metric space over Z_n and I think that would work
but the problem is that it treats every element equally.

What I mean is that in some cases its more important that the first location
be the same than the second, etc...

I could measure them with something like

sum(|k-l|^(n-k),k=0..n) where w_k = w*_l, p1 = (w_0, ..., w_n) and p2 =
(w*_0, ..., w*_n)

or even something like

sum(|w(k)*(k-l)|,k=0..n)

where w(k) is a weight function.

These might violate the standard definition of a metric and there might be
some inconsistancies in my criteria. Just some idea. Obviously if two
permutations are the same then there "distance" should be 0.

The reason is that I want to see how "good" a permutation, picked at random,
is to a fixed permutation.

if I have something like

as the fixed permutation and I "randomly" choose
(4,2,5,3,1)

then its a pretty good "match" compared to (3,1,5,2,4) (which seems to be
the worse possible choice). Although I also would like to take into account
the order in which I'm right too.

if (4,2,5,1,3) is the fixed permutation,

then (2,4,5,1,3) is much worse then (4,2,5,3,1)

Thanks,
Jon

digfarenough@gmail.com · science forum beginner Joined: 03 Apr 2006 Posts: 10

I would suggest that the simplest metric is just the number of element
swaps needed to turn one permutation into another (i.e. (4,2,5,1,3) is
one swap away from (4,2,5,3,1)), but it seems you want an explicit
formula for calculating the distance between two and I'm not sure how
easy it would be to express the above as a formula. I do believe it
satisfies the triangle inequality, though.

A start would be to consider the number of positions that differ
between two cases, which would be 0 or >=2 if the permutations are the
same length. But 4 elements being different could be solved by 2 to 4
swaps, depending on the specific permutation.

http://forums.wolfram.com/mathgroup/archive/2000/Jan/msg00251.html
contains an algorithm for computing distances in this sense, so it
might be a start.

Peter Webb · science forum Guru Wannabe Joined: 05 May 2005 Posts: 192

"Abstract Dissonance" <Abstract.Dissonance@hotmail.com> wrote in message
news:1251nmnholiebc3@corp.supernews.com...

Gene Ward Smith · science forum Guru Joined: 08 Jul 2005 Posts: 409

Abstract Dissonance wrote:

Abstract Dissonance · science forum Guru Wannabe Joined: 29 Dec 2005 Posts: 201

<digfarenough@gmail.com> wrote in message
news:1146151480.211584.143210@g10g2000cwb.googlegroups.com...

Abstract Dissonance · science forum Guru Wannabe Joined: 29 Dec 2005 Posts: 201

"Peter Webb" <webbfamily-diespamdie@optusnet.com.au> wrote in message
news:4450e463$0$10672$afc38c87@news.optusnet.com.au...

Abstract Dissonance · science forum Guru Wannabe Joined: 29 Dec 2005 Posts: 201

"Gene Ward Smith" <genewardsmith@gmail.com> wrote in message
news:1146166688.767956.60470@i40g2000cwc.googlegroups.com...

kunzmilan@atlas.cz · science forum beginner Joined: 21 Feb 2006 Posts: 42

Distances between permutations can be measured using Spearman
correlation coefficient. The sum of differences of positions of all
objects permuted as compared to the basic unit permutation is always 0.
These differences can be either positive or negative. The sum of
squared differences must be necessarily positive. These differences of
positions can be treated as distances in the cubes.

kunzmilan@atlas.cz · science forum beginner Joined: 21 Feb 2006 Posts: 42

Distances between permutations can be measured using Spearman
correlation coefficient. The sum of differences of positions of all
objects permuted as compared to the basic unit permutation is always 0.
These differences can be either positive or negative. The sum of
squared differences must be necessarily positive. These differences of
positions can be treated as distances in the cubes.

Google