MathGroup Archive 1997

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

Search the Archive

Re: Re: programing: reduce list to cycle


mathgroup at smc.vnet.net
S[mg8650] Re: programing: reduce list to cycle


>This is the second summary of the problem shortest Cycle posted  
>around(1997/09).
> Problem:
>
> I want to reduce a list to its shortest cycle. For example, if
> myList={3,1,0,3,3,1,0,3,3,1,0,3}, then the desired result should be
> {3,1,0,3}. How to do it? myList are not always complete cycles,  
in > such case, the whole list should be returned.


Xah,

Here are two variations using Wouter's elegant test for cycles.

Clear[shortestCycleAlanH2];
shortestCycleAlanH2[li_]:=
  Scan[ If[RotateRight[li,#]===li, Return[Take[li,#]]]&,
  	Divisors[Length[li]]
  ]


Clear[shortestCycleAlanH3];
shortestCycleAlanH3[li_]:=
  Scan[If[Take[li,#]===Take[li,-#] && RotateRight[li,#]===li,
        Return[Take[li,#]]]&,
	Divisors[Length[li]]
  ]

Timings, based on tests in your last posting

shortestCycleAlanH2[niceCycle]//Timing//First
shortestCycleAlanH3[niceCycle]//Timing//First
shortestCycleWouter[niceCycle]//Timing//First
shortestCycleWillS[niceCycle]//Timing//First

0.26551 Second
0.140578 Second
0.421858 Second
0.906252 Second

shortestCycleAlanH2[notCycle];//Timing//First
shortestCycleAlanH3[notCycle];//Timing//First
shortestCycleWouter[notCycle];//Timing//First
shortestCycleWillS[notCycle];//Timing//First

0.249733 Second
0.109364 Second
651.139 Second
0.640604 Second

Allan Hayes
hay at haystack.demon.co.uk
http://www.haystack.demon.co.uk/training.html
voice:+44 (0)116 2714198
fax: +44 (0)116 2718642
Leicester,  UK


  • Prev by Date: Re: NonLinearFit
  • Next by Date: Re: Points to Funciton
  • Previous by thread: Re: Re: programing: reduce list to cycle
  • Next by thread: Re: Flat: Problems & Workarounds