       Re: Product of transpositions

• To: mathgroup at smc.vnet.net
• Subject: [mg17345] Re: [mg17318] Product of transpositions
• From: Ken Levasseur <Kenneth_Levasseur at uml.edu>
• Date: Mon, 3 May 1999 01:45:52 -0400
• Organization: UMass Lowell Mathematical Sciences
• References: <199905010322.XAA25737@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

```Carl:

The collection of packages called AbstractAlgebra
(http://www.central.edu/homepages/hibbarda/EAAM/eaam.html) contains
functions to do what you want.  The default multiplication order is
right to left:

In:=
Needs["AbstractAlgebra`Master`"]

Here's an example of your starting data:

In:=
trans={{1,5},{2,4},{3,1},{2,6},{3,7},{1,3},{3,5}}
Out=
{{1, 5}, {2, 4}, {3, 1}, {2, 6}, {3, 7}, {1, 3}, {3, 5}}

Turn the data into a form used by our packages.
In:=
cyclelist=Apply[Cycle,trans,1]
Out=
{Cycle[1, 5], Cycle[2, 4], Cycle[3, 1], Cycle[2, 6],
Cycle[3, 7], Cycle[1, 3], Cycle[3, 5]}

The next result is a list of images (1->7, 2->6, ...)
In:=
MultiplyCycles@@cyclelist
Out=
{7, 6, 1, 2, 3, 4, 5}

A representation of the result as a product of disjoint cycles:

In:=
ToCycles[%]
Out=
{Cycle[1, 7, 5, 3], Cycle[2, 6, 4]}

I tried 120 random transpositions from Range[1,50] (you didn't say what
n was) and it took almost 20 sec. on my old Mac 7200.  I don't know if
that's fast enough for you.  Al Hibbard and I extended the functions
that are in DiscreteMath`Permutations` to work with cycles, but we also
have lots of other group and ring operations included.  You probably can
speed up the process by extracting our MultiplyCycles and using DiscreteMath`Permutations`

Ken Levasseur
Math. Sci.
UMass Lowell

Carl Woll wrote:
>
> 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: Re: LogLog scales with contourplots
• Next by Date: help needed
• Previous by thread: Product of transpositions
• Next by thread: Re: Product of transpositions