AnswerBun.com

Find cycle length in a list

Mathematica Asked by Nico A on September 24, 2020

I have a list of lists of numbers:

{{5,2,1},{8,1,3},{6,1,1,1},{8,1,3},{6,1,1,1},{8,1,3}}

As you can see, they eventually cycle, but not immediately. I need a function that will take a list of lists of numbers like this and return the cycle length (in this case $2$), and I need it to be as fast as possible.

The naive way is to take the first element that appears more than once, find it’s first two positions in the list and subtract them:

findCycle[list_] := (tbl = 
   Flatten[Position[list, Select[list, (Count[list, #] > 1 &)][[1]]]];
   tbl[[2]] - tbl[[1]])

But this is slower than I’d like, and it errors when there is not a cycle. I’ll be running this on ~25000 lists of 500 items.

3 Answers

Just for tip:

 data = ContinuedFraction[(Sqrt[12] + 2)/7, 10004];
    
 Timing[[email protected]@FindTransientRepeat[data, 2]]
 {0.0624004, 6}
 
 Timing[[email protected]@[email protected][data, [email protected]]]
 {0.0156001, 6}

Answered by lesobrod on September 24, 2020

FindTransientRepeat

periodF1 = Length @ Last @ FindTransientRepeat[#, 2]&; 

lst = {{5, 2, 1}, {8, 1, 3}, {6, 1, 1, 1}, {8, 1, 3}, {6, 1, 1, 1}, {8, 1, 3}};
periodF1 @ lst

2

Answered by kglr on September 24, 2020

ll = {};
Reap[
  Do[
    If[MemberQ[ll, i], 
      Sow[Length[ll] - Flatten[Position[ll, i]] + 1]; Break[], 
      AppendTo[ll, i]
    ],
    {i, list}
  ]
][[2]]

We can use Break to stop loop when duplicate value is found

Answered by XinBae on September 24, 2020

Add your own answers!

Related Questions

Plot of Implicit Equations

4  Asked on December 18, 2020 by diverger

 

Consistent pixel assignments in ClusteringComponents?

1  Asked on December 18, 2020 by christopher-moore

   

Errors in Lyapunov exponent code

1  Asked on December 17, 2020 by disp0sable_h3r0

     

How to reverse the arrows in a graph?

1  Asked on December 17, 2020 by ablmf

 

Getting message Solve::itdim

0  Asked on December 17, 2020 by somayeh

     

Generating a list of outputs using For[] Loop

1  Asked on December 17, 2020 by user75376

 

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP