Re: Re: programing: reduce list to cycle

• To: mathgroup at smc.vnet.net
• Subject: [mg8677] Re: [mg8650] Re: programing: reduce list to cycle
• From: Allan Hayes <hay at haystack.demon.co.uk>
• Date: Mon, 15 Sep 1997 02:49:04 -0400
• Sender: owner-wri-mathgroup at wolfram.com

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