speed of the ToCycles[] function

*To*: mathgroup at smc.vnet.net*Subject*: [mg9302] speed of the ToCycles[] function*From*: "W. Meeussen" <w.meeussen.vdmcc at vandemoortele.be>*Date*: Mon, 27 Oct 1997 02:47:13 -0500*Sender*: owner-wri-mathgroup at wolfram.com

hi group, in the DiscreteMath`Permutations` package lives the "ToCycles[]" function as written by Steve Skienna. I found that it can be accelerated by a factor of at least two. In some applications, its speed is the main time consumer, so speeding it up is worthwhile. It might be a good idea to do timing tests with permutations that either produce few large cycles, or a lot of small cycles. Since members of this group have drastically different programming styles, and can be tenacious in their attempts to find "optimal algorithms", it seems a good idea to try. here is my bit: mytocycles[perm_List] := DeleteCases[Table[Module[{predi = Position[perm, i][[1,1]], fpl}, fpl = If[i > 1 && predi < i, Null, Drop[FixedPointList[If[perm[[#1]] <= i, predi, perm[[#1]]] & , i], -1]]; If[fpl === Null || perm[[fpl[[-Min[Length[fpl], 2]]]]] =!= fpl[[-1]] || fpl[[1]] =!= Min[fpl], Null, fpl]], {i, 1, Length[perm]}], Null] As the timing results below show, "mytocycles[]" has a bit of an advantage for the "many short cycles" -case. It attains about the same speed for the "few long cycles" -case when the permutation length is over 200. In[14]:= n=501; perm=RandomPermutation[n]; manyshort=FromCycles at Partition[perm,3]; fewlong=FromCycles at Partition[perm,Floor[n/3]]; Timing[a=ToCycles[manyshort];] Timing[b=RotateLeft/@mytocycles[manyshort];] a==b Timing[d=ToCycles[fewlong];] Timing[e=RotateLeft/@mytocycles[fewlong];] d==e Out[18]= {209.49 Second, Null} Out[19]= {3.24 Second, Null} Out[20]= True Out[21]= {4.22 Second, Null} Out[22]= {3.85 Second, Null} Out[23]= True Dr. Wouter L. J. MEEUSSEN w.meeussen.vdmcc at vandemoortele.be eu000949 at pophost.eunet.be