Re: Re: programing: reduce list to cycle

• To: mathgroup at smc.vnet.net
• Subject: [mg8625] Re: [mg8615] Re: programing: reduce list to cycle
• From: "C. Woll" <carlw at u.washington.edu>
• Date: Fri, 12 Sep 1997 04:10:39 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```Hi Xah,

I have a comment on Will Self's solution. Instead of factors, one could
just use the built in function Divisors:

?Divisors

Divisors[n] gives a list of the integers that divide n.

Carl Woll
Dept of Physics
U of Washington

On Tue, 9 Sep 1997, Xah wrote:

> This is a summary of the shortest cycle problem.
> 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.
>
> Solutions:
> (*from a friend*)
>
> shortestCycle[lis_List] :=
>         With[{l = Length[lis]},
>         Take[lis, Do[If[Mod[l,i]===0 && MatchQ[Partition[lis,i],{(x_)..}],
>           Return[i]],{i,1,l}]]];
>
> (*from Will Self wself at viking.emcmt.edu*)
>
> repe[x_List,n_Integer?Positive]:=Flatten[Table[x,{n}],1]
>
> factors[n_Integer?Positive]:= If[n==1,1,
> Sort[Flatten[Outer[Times,
> Sequence@@(Table[#[[1]]^x,{x,0,#[[2]]}]& /@ FactorInteger[n]) ]]]]
>
> minrep[x_List]:=  Module[{m,f,temp},
> m=Length[x];f=factors[m];
> Do[If[repe[temp=Take[x,f[[k]] ],m/f[[k]]] == x,
>    Return[temp]],{k,1,Length[f]}]]
>
> (*Speed comparison*)
>
> cycList=Table[Random[Integer,{1,9}],{i,1,20}]
> niceCycle=Flatten at Table[cycList,{i,1,1000}];
> notCycle=Flatten[{niceCycle,a}];
> Length at Flatten@niceCycle
>
> {2,9,4,4,1,4,8,6,1,3,7,9,2,9,6,4,5,9,7,5}
>
> 20000
>
> a1=Timing at shortestCycle[niceCycle];
> a2=Timing at minrep[niceCycle];
>
> b1=Timing at shortestCycle[notCycle];
> b2=Timing at minrep[notCycle];
>
> (First/@{a1,a2})
> (First/@{b1,b2})
>
> {1.11667 Second,0.933333 Second}
>
> {3.56667 Second,0.966667 Second}
>
> Equal@(Last/@{a1,a2})&&Equal@(Last/@{b1,b2})
>
> True
> ----------------
>
> They are both based on the same principle: by testing the divisibility of
> the length of the list, then compare original to a created list. The former
> is easy to understand, the latter is faster. There should be a pure pattern
> matching solution.
>
>  Xah
>  xah at best.com
>  http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html
>  Mountain View, CA, USA
>
>

```

• Prev by Date: Re: programing: reduce list to cycle
• Next by Date: Re: Help with Iteration.
• Previous by thread: Re: programing: reduce list to cycle
• Next by thread: Re: Re: programing: reduce list to cycle