27
$\begingroup$

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.

Related links

MATLAB function seqperiod()

SO question on cycle detection

Related question on this site

Wikipedia article on cycle detection

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – QuestionC
    Apr 17, 2015 at 16:05
  • $\begingroup$ @QuestionC The answer to that question that compares all other answers is great. $\endgroup$
    – VividD
    Apr 17, 2015 at 16:12
  • 1
    $\begingroup$ For the case of missing or corrupted values, there is some discussion in this MathGroup thread $\endgroup$
    – Daniel Lichtblau
    Apr 17, 2015 at 19:12
  • 1
    $\begingroup$ 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!) $\endgroup$
    – David Zhang
    Apr 17, 2015 at 21:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Z
    Apr 19, 2015 at 8:57

8 Answers 8

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ admire your cleverness, +1 $\endgroup$
    – matheorem
    Oct 29, 2015 at 1:17
12
$\begingroup$ 
ClearAll[len]

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

len /@ lists
(* {2, 3, 14} *)
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Are you sure you want to use .. instead of ...? If p has only one partial repeat, above construct doesn't quite get it. $\endgroup$
    – kirma
    Apr 17, 2015 at 16:48
  • $\begingroup$ @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. $\endgroup$
    – C. E.
    Apr 17, 2015 at 18:12
  • $\begingroup$ Very nice. +1 . $\endgroup$
    – ciao
    Apr 18, 2015 at 3:30
  • $\begingroup$ @Pickett for my application it is not so critical to make such distinction or not, but I would think your way $\endgroup$
    – VividD
    Apr 18, 2015 at 8:08
11
$\begingroup$

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

enter image description here

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

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:

enter image description here

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.
Improve this answer
$\endgroup$
6
7
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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

enter image description here

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]]}] &;
Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for introducing me to "Periodic" argument of PadRight :) $\endgroup$
    – ubpdqn
    Apr 19, 2015 at 7:53
  • $\begingroup$ @ubpdqn, just noticed this usage for PadRight and PadLeft is still undocumented. $\endgroup$
    – kglr
    Apr 19, 2015 at 8:09
6
$\begingroup$

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}

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This should be the accepted answer for v11.2+ $\endgroup$
    – flinty
    Jul 6, 2020 at 19:55
3
$\begingroup$

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}}}
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.