Python在整数列表中查找重复序列？

Question

我有一个列表列表,每个列表都有一个重复序列.我正在尝试计算列表中重复的整数序列的长度:

list_a = [111,0,3,1,111,0,3,1,111,0,3,1] 

list_b = [67,4,67,4,67,4,67,4,2,9,0]

list_c = [1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,23,18,10]

哪个会回归:

list_a count = 4 (for [111,0,3,1])

list_b count = 2 (for [67,4])

list_c count = 10 (for [1,2,3,4,5,6,7,8,9,0])

欢迎任何建议或提示.我现在正试着用re.compile解决这个问题,但是,它不太正确.

Answer 1

通过迭代序列长度的2到一半之间的猜测来猜测序列长度.如果未发现任何模式,则默认返回1.

def guess_seq_len(seq):
    guess = 1
    max_len = len(seq) / 2
    for x in range(2, max_len):
        if seq[0:x] == seq[x:2*x] :
            return x

    return guess

list_a = [111,0,3,1,111,0,3,1,111,0,3,1] 
list_b = [67,4,67,4,67,4,67,4,2,9,0]
list_c = [1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,23,18,10]

print guess_seq_len(list_a)
print guess_seq_len(list_b)
print guess_seq_len(list_c)
print guess_seq_len(range(500))   # test of no repetition

这给出了(如预期的那样):

4
2
10
1

根据要求,该替代方案给出了最长的重复序列.因此它将为list_b返回4.唯一的变化是guess = x代替return x

def guess_seq_len(seq):
    guess = 1
    max_len = len(seq) / 2
    for x in range(2, max_len):
        if seq[0:x] == seq[x:2*x] :
            guess = x

    return guess