Decomposition of a permutation into a product of transpositions

[Alexander Paul]

Hello!

# I'm looking for an algorithm to decompose an arbitrary permutation
into a product of pairwise transpositions so that their number is as
minimal as possible. #

This problem could be solved using bubble sort, but this method is slow
and doesn't take into account, that not only neighbour entries can be
transposed.

Unfortunately I haven't managed to find a more effective way yet. :-(

I would be most grateful for any help or ideas...

:)

Alex

[Proginoskes]

Decompose the permutation into the product of disjoint cycles; then
work with each cycle. (The optimization problem for cycles should be
trivial, or nearly so.)

--- Christopher Heckman

[Virgil]

In article <1144041874.5...@z34g2000cwc.googlegroups.com>,
"Alexander Paul" <alexande...@yahoo.de> wrote:

How about a two tier algorithm:

First decompose the permutation into disjoint cycles, which should be
quick and easy, discarding any 1-cycles.

Then decompose each of those disjoint cycles into a minimal number of
transpostions, which is also quick and easy.

The result will of necessity be a minimal number of transpositions.

The mimimal number of transpositions required for each cycle is one less
that the number of items in the cycle.

For example the cycle (a b c) carrying a to b, b to c and c back to a
decomposes into transpositions (a b)(a c)

[Alexander Paul]

Virgil wrote:

> How about a two tier algorithm:
>
> First decompose the permutation into disjoint cycles, which should be
> quick and easy, discarding any 1-cycles.
>
> Then decompose each of those disjoint cycles into a minimal number of
> transpostions, which is also quick and easy.

Proginoskes wrote:

> Decompose the permutation into the product of disjoint cycles; then
> work with each cycle. (The optimization problem for cycles should be
> trivial, or nearly so.)

Thanks! :-)

It works great!

Alex

[Rick D.]

On Mon, 03 Apr 2006 00:55:07 -0600, Virgil
<ITSnetNOTcom#vir...@COMCAST.com> wrote:

[snip]

>How about a two tier algorithm:
>
>First decompose the permutation into disjoint cycles, which should be
>quick and easy, discarding any 1-cycles.
>
>Then decompose each of those disjoint cycles into a minimal number of
>transpostions, which is also quick and easy.
>
>The result will of necessity be a minimal number of transpositions.

Doesn't this leave out tactics that think forward multiple steps?
Where for example a value isn't placed at the right position right
away, but the resulting number of steps might still be smaller because
the numbers will interact in a way that makes the resulting swap path
shorter.

Best regards,
Rick D.