Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1997
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1997

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

Search the Archive

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