How to detect if a repeating pattern exists

Question

My question isn't language specific... I would probably implement this in C# or Python unless there is a specific feature of a language that helps me get what I am looking for.

Is there some sort of algorithm that anyone knows of that can help me determine if a list of numbers contains a repeating pattern?

Let's say I have a several lists of numbers...

[12, 4, 5, 7, 1, 2]
[1, 2, 3, 1, 2, 3, 1, 2, 3]
[1, 1, 1, 1, 1, 1]
[ 1, 2, 4, 12, 13, 1, 2, 4, 12, 13]

I need to detect if there is a repeating pattern in each list... For example, list 1 returns false, but and lists 2, 3, and 4 return true.

I was thinking maybe taking a count of each value that appears in the list and if val 1 == val 2 == val n... then that would do it. Any better ideas?

Answer 1

You want to look at the autocorrelation of the signal. Autocorrelation basically does a convolution of the signal with itself. When a you iteratively slide one signal across another, and there is a repeating pattern, the output will resonate strongly.

Answer 2

The second and fourth strings are periodic; I'm going to assume you're looking for an algorithm for detecting periodic strings. Most fast string matching algorithms need to find periods of strings in order to compute their shifting rules.

Knuth-Morris-Pratt's preprocessing, for instance, computes, for every prefix P[0..k] of the pattern P, the length SP[k] of the longest proper suffix P[s..k] of P[0..k] that exactly matches the prefix P[0..(k-s)]. If SP[k] < k/2, then P[0..k] is aperiodic; otherwise, it is a prefix of a string with period k - SP[k].