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
- Follow-Ups:
- Re: Product of transpositions
- From: Daniel Lichtblau <danl>
- Re: Product of transpositions
- From: Ken Levasseur <Kenneth_Levasseur@uml.edu>
- Re: Product of transpositions