Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Product of transpositions

• To: mathgroup at smc.vnet.net
• Subject: [mg17396] Re: [mg17318] Product of transpositions
• From: Carl Woll <carlw at u.washington.edu>
• Date: Thu, 6 May 1999 02:44:13 -0400
• Organization: Physics Department, U of Washington
• References: <199905010322.XAA25737@smc.vnet.net.> <372B163F.62E01DE9@uml.edu>
• Sender: owner-wri-mathgroup at wolfram.com

Ken and David,

Thanks for your reply. Unfortunately, it's a little slow. Here's a comparison with the
function I gave in my post.

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

In[2]:=
toRule[{a_Integer,b_Integer}]:={a->b,b->a}
toPerm[t:{{_Integer,_Integer}..}]:=
  Fold[ReplaceAll,Range[Max[t]],toRule/@Reverse[t]]

In[4]:=
swaps=Table[{Random[Integer,{1,100}],Random[Integer,{1,100}]},{100}];
cyc=Apply[Cycle,swaps,1]/.Cycle[n_,n_]->Sequence[];

In[5]:=
a1=MultiplyCycles[cyc];//Timing
a2=toPerm[swaps];//Timing
a1===a2

Out[5]=
{13.06 Second,Null}

Out[6]=
{0.13 Second,Null}

Out[7]=
True

As you can see, the function toPerm is 2 orders of magnitude faster. If I choose a smaller
range for the random integers, the difference in speed is comparable. For your information, I
extended the definition of toPerm to handle cycles of any length, and it was ~20 times faster
than MultiplyCycles. So, I'm still wondering if toPerm is the optimal solution.

--
Carl Woll
Dept of Physics
U of Washington

Ken Levasseur wrote:

> 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>