# Finding the period of an array of integers

A simple array of integers is given. The problem is to detect if a pattern is repeatedly occurring in the array, and find the length of that pattern.

For example, for

{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6}


pattern {19, 6} should be detected and its length is 2.

For

{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7}


pattern {73, 7, 4} should be detected and its length is 3. (at the end of the array there need not be the complete pattern, but the pattern should start at the beginning of the array)

For

{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}


the whole array is the pattern and its length is 14.

MATLAB function seqperiod()

SO question on cycle detection

Related question on this site

Wikipedia article on cycle detection

• This problem was solved in python pretty cleverly not too long ago. stackoverflow.com/questions/29481088/… I suspect that algorithm is going to be the cleanest and fastest solution in any high-level language that supports finding sequences within a list. Apr 17, 2015 at 16:05
• @QuestionC The answer to that question that compares all other answers is great. Apr 17, 2015 at 16:12
• For the case of missing or corrupted values, there is some discussion in this MathGroup thread Apr 17, 2015 at 19:12
• I wonder if a clever solution based on Fourier is possible here? (I'm the guy who came up with the (s+s).find(s, 1, -1) solution, btw--flattered to see it's gotten so much attention!) Apr 17, 2015 at 21:19
• @QuestionC actually I don't think that algorithm works here, because in this question the cycle does not have to be complete at the end of the list. For example {1,2,3,1,2,3,1,2} should display a cycle length of 3, but the concatenate-and-search algorithm would indicate that the string is not periodic. Apr 19, 2015 at 8:57

This uses partitioning, with padding if required, to make sublists.

f = Module[{b, c = 1},
While[Length[b = Union@Partition[#, c, c, {1, 1}, Take[#, c]]] > 1, c++];
{Length@First@b, First@b}] &;


Example

f@{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7}


{3, {73, 7, 4}}

ClearAll[len]

len[{p__, p__ .., e___}] /; MatchQ[{p}, {e, __}] := Length[{p}]
len[p_] := Length[p]

len /@ lists
(* {2, 3, 14} *)

• Are you sure you want to use .. instead of ...? If p has only one partial repeat, above construct doesn't quite get it. Apr 17, 2015 at 16:48
• @kirma Yes, I consciously made it that way because I didn't consider p to be a pattern if it never fully repeats itself. For example I thought it best that {1, 2, 7, 3, 5, 1} should be counted as one pattern of length six, instead of a pattern of length five. It depends on what the solution is used for I suppose. Apr 17, 2015 at 18:12
• Very nice. +1 .
– ciao
Apr 18, 2015 at 3:30
• @Pickett for my application it is not so critical to make such distinction or not, but I would think your way Apr 18, 2015 at 8:08

I won't bet my hand for this but seems to be ok:

ClearAll[return];
return[x : {0 ..., 1}, list_] := {#, list[[;; #]]} &[Length@x];
return[x_, y_] := {Length@y, y};

sqPeriod[list_] := return[FindLinearRecurrence[list], list]

sqPeriod /@ {
{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6},
{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7},
{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}
} // Column


• Fails for patterns with length 1: In[1]:= sqPeriod[{1, 1, 1, 1, 1, 1}]; Out[1]= {6, {1, 1, 1, 1, 1, 1}} Apr 17, 2015 at 13:11
• @Gerli Thanks, fixed.
– Kuba
Apr 17, 2015 at 13:11
• +1, yours among the ones that seems to get it right, and pretty quickly.
– ciao
Apr 18, 2015 at 7:52
• @rasher Thanks :) I like that MMA lets me skip thinking process sometimes :P
– Kuba
Apr 19, 2015 at 8:12
• @Kuba sqPeriod@{73, 7, 4, 73, 7, 4} gives wrong answer, check it out :) Oct 29, 2015 at 0:48

This answer only returns the period. If you want to extract the repeating substring, just use Take[list, period].

sequencePeriod = Compile[{{l, _Integer, 1}},
With[{n = Length[l]},
Catch[
Do[
If[
Catch[
Do[
Do[
If[l[[j]] != l[[k]], Throw[False]];,
{k, i + j, n, i}
];,
{j, i}
];
Throw[True];
],
Throw[i];
];,
{i, Quotient[n, 2]}
];
Throw[n];
]
]
]


For each trial period i, I go through the elements j of the trial list (1 through i) and make sure that each one is repeated in each subsequent copy of the list (k, offset from j by multiples of the period i).

This is the fastest solution so far:

I generated the lists for these tests with

Join @@ ConstantArray[RandomInteger[n, n], {n}]

• Pickett's solution is the most elegant, but seems to have exponential complexity.
• Kuba's has around quartic complexity due to the generality of FindLinearRecurrence.
• Chris has cubic performance, since he splits and compares the entire list at each trial period.
• My solution has quadratic performance, since we stop comparison as soon as we encounter a nonmatching element. It also has low memory usage, since I don't manipulate the array at all.
• Fast is nice, when it's fast and correct. This fails, e.g. {1,2,3,1,2} should return 3 per OP, this returns 5.
– ciao
Apr 18, 2015 at 17:54
• @rasher change Quotient[n,2] to n to get that behavior. Apr 18, 2015 at 18:04
• Please note that in your answer so readers can't miss it, and update benchmark to show the significant performance impact this change has.
– ciao
Apr 18, 2015 at 18:17
• @rasher Also, the performance difference is exactly zero for lists that do have a repeat (excepting a difference of one clock cycle for the /2/>>1), and the difference is around 2x for (random) lists with no repeats. Apr 18, 2015 at 18:36

In versions 10+, there is FindTransientRepeat:

• FindTransientRepeat[list, n] returns a pair of lists {transient,repeat} where the elements of repeat occur successively at least n times at the end of list.
• FindTransientRepeat accepts an incomplete copy of the repeated sublist in the last position
• The minimum number of repetitions refers to complete repetitions

For the examples in the posted question

lists = {{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6},
{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7},
{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}};


we get

FindTransientRepeat[#, 2]& /@ lists


{{{}, {19, 6}},
{{}, {73, 7, 4}},
{{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17}, {7}}}

We can define a function that processes the output of FindTransientRepeat to get the results in desired form:

Clearall[repeatsF]
repeatsF = Module[{ftr = FindTransientRepeat[#, 2], lst = #},
If[First @ ftr === {}, {Length @ Last @ ftr, Last @ ftr}, {Length @ lst, lst}]]&;

repeatsF /@ lists


{{2, {19, 6}},
{3, {73, 7, 4}},
{14, {73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}}}

Using the undocumented "Periodic" padding as the third argument of PadRight:

ClearAll[fpF, fpF2]
fpF = Block[{i = 1}, While[i < Length@# &&
PadRight[#[[;; i]], Length@#, "Periodic"] != #, i++]; i] &;
fpF2 = Block[{i = 1}, While[i < Length@# &&
PadRight[#[[;; i]], Length@#, "Periodic"] != #, i++]; {i, #[[;; i]]}] &;


Examples: Using tc from @ubpdqn's answer:

tc = {{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6},
{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7},
{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7},
{6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3, 3},
{6, 1, 6, 2, 6, 3, 6, 1, 6, 2, 6, 3, 6, 1, 6, 2},
{1, 1, 1},
{1, 2, 1, 2, 1}};

fpF /@ tc
(* {2, 3, 14, 5, 6, 1, 2} *)

{#, ## & @@ fpF2@#} & /@ tc // Grid[#, Dividers -> All] &
(* or {#,fpF @ #, #[[;;fpF @ #]]}&/@tc //Grid *)


If a complete periodic pattern were sought, we could search for periods less than or equal to half the Length of the input list:

ClearAll[fpFa, fpFb]
fpFa = Block[{i = 1, n = Length@#},  While[i < 1 + n/2 &&
PadRight[#[[;; i]], n, "Periodic"] != #, i++]; i = If[i < 1 + n/2, i, n]] &;
fpFb = Block[{i = 1, n = Length@#}, While[i < 1 + n/2 &&
PadRight[#[[;; i]], n, "Periodic"] != #, i++]; i = If[i < 1 + n/2, i, n];
{i, #[[;; i]]}] &;

• thank you for introducing me to "Periodic" argument of PadRight :) Apr 19, 2015 at 7:53
• @ubpdqn, just noticed this usage for PadRight and PadLeft is still undocumented.
– kglr
Apr 19, 2015 at 8:09

FindRepeat meets your need perfectly.

FindRepeat[{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6}]


{19, 6}

FindRepeat[{73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7, 4, 73, 7}]


{73, 7, 4}

FindRepeat[{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}]


{73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7, 7}

• This should be the accepted answer for v11.2+ Jul 6, 2020 at 19:55

Late to party, and liking all answers but esp Chris Degnen:

per[u_] := Module[{j = 1, lg = Length@u},
While[Total[
Abs[Take[Join @@ ConstantArray[u[[;; j]], Ceiling[lg/j]], lg] -
u]] != 0, j++]; {j, u[[;; j]]}]


Some test cases:

tc={{19, 6, 19, 6, 19, 6, 19, 6, 19, 6, 19, 6}, {73, 7, 4, 73, 7, 4, 73,
7, 4, 73, 7, 4, 73, 7}, {73, 7, 4, 7, 2, 6, 7, 2, 7, 73, 9, 17, 7,
7}, {6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3, 3, 6, 3, 6, 3,
3}, {6, 1, 6, 2, 6, 3, 6, 1, 6, 2, 6, 3, 6, 1, 6, 2}, {1, 1, 1}, {1,
2, 1, 2, 1}}


Testing: per/@tc

yields:

{{2, {19, 6}}, {3, {73, 7, 4}}, {14, {73, 7, 4, 7, 2, 6, 7, 2, 7, 73,
9, 17, 7, 7}}, {5, {6, 3, 6, 3, 3}}, {6, {6, 1, 6, 2, 6,
3}}, {1, {1}}, {2, {1, 2}}}