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