Re: Info about a particular permutation distance

From: Edwin Clark (eclark_at_math.usf.edu)
Date: 09/01/04 

Date: Wed, 01 Sep 2004 01:33:20 GMT

Joaqu?n M? L?pez Mu?oz wrote:
> I've scanned the net searching for various
> permutation distance definitions, and didn't find
> anything specifically related with this:
>
> A *move* is a permutation for which only one element
> is repositioned. For example, in
>
> 1 2 3 4 5 6 7 8
> 1 2 3 8 4 5 6 7
>
> the element 8 is repositioned from the 8th to the
> 4th place. Please note that a move is not a
> transposition: in fact, a transposition involves two
> moves in general.
>
> Now, the move distance between two permutations
> P1 and P2 is the minimum number of moves needed
> to obtain P2 from P1.
>
> Has this been studied anywhere? I'm looking
> for algorithms (exact or approximate) to compute
> moves. There seems to be abundant literature
> about transpositions, but not for this other type
> of simple operation.
>
> Joaquín M López Muñoz
> Telefónica, Investigación y Desarrollo

Se puede encontrar esto y mucho mas sobre "metrics on permutations" en
el libro:

Group Representations in Probablity and Statistics.
por Persi Diaconis.

He describes several metrics on S_n. The 5th one on page 112 is the one
you describe. He attributes this to Cayley and mentions that Cayley
proved that the distance from permutation f to permutation g in S_n is
given by n - # cycles in the disjoint cycle decomposition of fg^(-1).

Edwin Clark

---------------------------------------------------------
   W. Edwin Clark, Math Dept, University of South Florida
            http://www.math.usf.edu/~eclark/
---------------------------------------------------------

Relevant Pages

  • Re: Travelling salesman problem in C
    ... For every permutation you calculate the distance. ... If it is smaller than the minimum distance you have ... I see that the combination ACB> ABC therefore i skip the whole ACB ...
    (comp.lang.c)
  • Re: Challenae question for mathematician
    ... a sequence of number ... is the identity permutation; ... cancellations making the distance from x to z smaller. ... relatively straighforward to find the S-length of any given element, ...
    (sci.math)
  • Re: Travelling salesman problem in C
    ... For every permutation you calculate the distance. ... If it is smaller than the minimum distance you have ... I see that the combination ACB> ABC therefore i skip the whole ACB ...
    (comp.lang.c)
  • Re: permutations and inner products
    ... A well-known definition of distance between permutations in permutation ... Given a set X that is at most countably infinite, ... There is a natural analogue of this topological space that does not ...
    (sci.math)
  • Re: Maximum over an n-cycle
    ... and a permutation s in S_n, ... What I actually proved is that no _transposition_ of the ... A version of my question was indeed one of the easier Putnam problems ... I already knew that the sum S can be increased by transposing ...
    (sci.math)