Product of transpositions

• To: mathgroup at smc.vnet.net
• Subject: [mg17318] Product of transpositions
• From: Carl Woll <carlw at u.washington.edu>
• Date: Fri, 30 Apr 1999 23:22:38 -0400
• Organization: Physics Department, U of Washington
• Sender: owner-wri-mathgroup at wolfram.com

```Hi group,

I have a question/challenge.

Given a list of transpositions

{{a,b},{c,d},{e,f},...}

where a,b,c... are all positive integers less than or equal to n,
produce the permutation, or cyclic decomposition of the product of the
transpositions. I don't care if you choose to multiply transpositions
left to right or right to left. As an example, the following list of
transpositions

{{a,b},{b,c}}

using right to left multiplication, will produce

a->a->b
b->c->c
c->b->a

or the cycle {a,b,c}. That is, using the usual notation, (ab)(bc)=(abc).
I hope this is clear.

If this functionality is built into a standard package, then tell me the
package. Otherwise, what is the fastest implementation that anyone can
come up with. I'm interested in repeatedly converting a random product
of 120 transpositions into the corresponding permutation.

Here is one idea.

toRule[{a_Integer,b_Integer}]:={a->b,b->a}

toPerm[t:{{_Integer,_Integer}..}]:=Fold[ReplaceAll,Range[Max[t]],torule/@t]

Can anyone come up with a better idea?

--
Carl Woll
Dept of Physics
U of Washington

```

• Prev by Date: Books on the front end
• Next by Date: exporting grafics as eps
• Previous by thread: Re: Books on the front end
• Next by thread: Re: Product of transpositions