Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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[1]:=
Needs["AbstractAlgebra`Master`"]


Here's an example of your starting data:

In[2]:=
trans={{1,5},{2,4},{3,1},{2,6},{3,7},{1,3},{3,5}}
Out[2]=
{{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[3]:=
cyclelist=Apply[Cycle,trans,1]
Out[3]=
{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[4]:=
MultiplyCycles@@cyclelist
Out[4]=
{7, 6, 1, 2, 3, 4, 5}

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

In[5]:=
ToCycles[%]
Out[5]=
{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

• References:
  • Product of transpositions
    • From: Carl Woll <carlw@u.washington.edu>