Find a period of eventually periodic sequence
<p><strong>Short explanation.</strong></p>
<p>I have a sequence of numbers <code>[0, 1, 4, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7, 0, 0, 1, 1, 2, 3, 7]</code>. As you see, from the 3-rd value the sequence is periodic with a period <code>[0, 0, 1, 1, 2, 3, 7]</code>.</p>
<p>I am trying to automatically extract this period from this sequence. The problem is that neither I know the length of the period, nor do I know from which position the sequence becomes periodic.</p>
<p><strong>Full explanation</strong> (might require some math)</p>
<p>I am learning combinatorial game theory and a cornerstone of this theory requires one to calculate <a href="https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem" rel="nofollow noreferrer">Grundy values</a> of a game graph. This produces infinite sequence, which in many cases becomes <a href="http://mathworld.wolfram.com/EventuallyPeriodic.html" rel="nofollow noreferrer">eventually periodic</a>.</p>
<p>I found a way to efficiently calculate grundy values (it returns me a sequence). I would like to automatically extract offset and period of this sequence. I am aware that seeing a part of the sequence <code>[1, 2, 3, 1, 2, 3]</code> you can't be sure that <code>[1, 2, 3]</code> is a period (who knows may be the next number is <code>4</code>, which breaks the assumption), but I am not interested in such intricacies (I assume that the sequence is enough to find the real period). Also the problem is the sequence can stop in the middle of the period: <code>[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, ...]</code> (the period is still <code>1, 2, 3</code>).</p>
<p>I also need to find the smallest offset and period. For example for original sequence, the offset can be <code>[0, 1, 4, 0, 0]</code> and the period <code>[1, 1, 2, 3, 7, 0, 0]</code>, but the smallest is <code>[0, 1, 4]</code> and <code>[0, 0, 1, 1, 2, 3, 7]</code>.</p>
<hr />
<p>My inefficient approach is to try every possible offset and every possible period. Construct the sequence using this data and check whether it is the same as original. I have not done any normal analysis, but it looks like it is at least quadratic in terms of time complexity.</p>
<p>Here is my quick python code (have not tested it properly):</p>
<pre class="lang-py prettyprint-override"><code>def getPeriod(arr):
    min_offset, min_period, n = len(arr), len(arr), len(arr)
    best_offset, best_period = [], []
    for offset in xrange(n):
        start = arr[:offset]
        for period_len in xrange(1, (n - offset) / 2):
            period = arr[offset: offset+period_len]
            attempt = (start + period * (n / period_len + 1))[:n]

            if attempt == arr:
                if period_len &lt; min_period:
                    best_offset, best_period = start[::], period[::]
                    min_offset, min_period = len(start), period_len
                elif period_len == min_period and len(start) &lt; min_offset:
                    best_offset, best_period = start[::], period[::]
                    min_offset, min_period = len(start), period_len

    return best_offset, best_period
</code></pre>
<p>Which returns me what I want for my original sequence:</p>
<pre class="lang-py prettyprint-override"><code>offset [0, 1, 4]
period [0, 0, 1, 1, 2, 3, 7]
</code></pre>
<p>Is there anything more efficient?</p>