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: programing: reduce list to cycle

  • To: mathgroup at smc.vnet.net
  • Subject: [mg8615] Re: programing: reduce list to cycle
  • From: "Xah" <xah at best.com>
  • Date: Tue, 9 Sep 1997 03:07:28 -0400
  • Organization: smtp.best.com
  • Sender: owner-wri-mathgroup at wolfram.com

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: Combining Lists?
  • Next by Date: REQ:Algorythm for combinations
  • Previous by thread: programing: reduce list to cycle
  • Next by thread: Re: programing: reduce list to cycle