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
>
>