Find pediodicity in a list

slate 1 Tallied Votes 163 Views Share

A brute force method.
Finds the FIRST and SHORTEST periodicity in the input list.

def find_period(inp):
    '''
    Finds the FIRST and SHORTEST periodicity in the list: inp. 
    Returns the position of the 0-based begin of the periodicity if any, and the length of it
    If it does not find any, returns None
    '''
    pos=0
    other=1
    adjust=0
    leninp=len(inp)
    while pos<leninp:
        try:
            other=inp.index(inp[pos],pos+1+adjust)
        except ValueError:
            other=None
        if other and other-pos<=leninp-other:
            for i in xrange(other,leninp):
                if inp[i-(other-pos)]!=inp[i]:
                    adjust+=1
                    break
            else:
                return pos, other-pos
        else:
            adjust=0
            pos+=1