determine if list is periodic python

Question

I am curious to find out a function to check if a given list is periodic or not and return the periodic elements. lists are not loaded rather their elements are generated and added on the fly, if this note will make the algorithm easier anyhow.

For example, if the input to the function is [1,2,1,2,1,2,1,2], the output shall be (1,2).

I am looking for some tips and hints on the easier methods to achieve this.

Thanks in advance,

Answer 1

This problem can be solved with the Knuth-Morris-Pratt algorithm for string matching. Please get familiar with the way the fail-links are calculated before you proceed.

Lets consider the list as something like a sequence of values (like a String). Let the size of the list/sequence is n.

Then, you can:

1. Find the length of the longest proper prefix of your list which is also a suffix. Let the length of the longest proper prefix suffix be len.

2. If n is divisible by n - len, then the list is periodic and the period is of size len. In this case you can print the first len values.

More info:

• GeeksForGeeks article.
• Knuth-Morris-Pratt algorithm

Answer 2

NOTE: the original question had python and python-3.x tags, they were edited not by OP, that's why my answer is in python.

I use itertools.cycle and zip to determine if the list is k-periodic for a given k, then just iterate all possible k values (up to half the length of the list).

try this:

from itertools import cycle


def is_k_periodic(lst, k):
    if len(lst) < k // 2:  # we want the returned part to repaet at least twice... otherwise every list is periodic (1 period of its full self)
        return False

    return all(x == y for x, y in zip(lst, cycle(lst[:k])))


def is_periodic(lst):
    for k in range(1, (len(lst) // 2) + 1):
        if is_k_periodic(lst, k):
            return tuple(lst[:k])
    return None


print(is_periodic([1, 2, 1, 2, 1, 2, 1, 2]))

Output:

(1, 2)

Answer 3

Thank you all for answering my question. Neverthelss, I came up with an implementation that suits my needs.

I will share it here with you looking forward your inputs to optimize it for better performance.

The algorithm is:

• assume the input list is periodic.
• initialize a pattern list.
• go over the list up to its half, for each element i in this first half:
  • add the element to the pattern list.
  • check if the pattern is matched throughout the list.
    • if it matches, declare success and return the pattern list.
    • else break and start the loop again adding the next element to the pattern list.
  • If a pattern list is found, check the last k elements of the list where k is len(list) - len(list) modulo the length of the pattern list, if so, return the pattern list, else declare failure.

The code in python:

def check_pattern(nums):
    p = []
    i = 0
    pattern = True
    while i < len(nums)//2:
        p.append(nums[i])
        for j in range(0, len(nums)-(len(nums) % len(p)), len(p)):
            if nums[j:j+len(p)] != p:
                pattern = False
                break
            else:
                pattern = True
        # print(nums[-(len(nums) % len(p)):], p[:(len(nums) % len(p))])
        if pattern and nums[-(len(nums) % len(p)) if (len(nums) % len(p)) > 0 else -len(p):] ==\
                p[:(len(nums) % len(p)) if (len(nums) % len(p)) > 0 else len(p)]:
            return p
        i += 1
    return 0

This algorithm might be inefficient in terms of performance but it checks the list even if the last elements did not form a complete period.

Any hints or suggestions are highly appreciated.

Thanks in advance,,,

Answer 4

Let L the list. Classic method is: use your favorite algorithm to search the second occurence of the sublist L in the list L+L. If the list is present at index k, then the period is L[:k]:

    L                     L
1 2 1 2 1 2 1 2 | 1 2 1 2 1 2 1 2
    1 2 1 2 1 2   1 2

(This is conceptually identical to @KonstantinYovkov's answer). In Python: example with strings (because Python has no builtin sublist search method):

>>> L = "12121212"
>>> k = (L+L).find(L, 1) # skip the first occurrence
>>> L[:k]
'12'

But:

>>> L = "12121"
>>> k = (L+L).find(L, 1)
>>> L[:k] # k is None => return the whole list
'12121'