python - Python find duplicate adjacent sequences in list

Question

I have a list of positive integer numbers (indices) and want to find cycles (here: duplicate adjacent sequences of list elements) as part of an iterative algorithm. The number of iterations is less than 10^6. In every iteration, one number is appended to the list (initially the list is empty) and the list should be checked for cycles. The list size should typically be less than 10^6, usually in the range 0 - 10^5, and the integers will likely be smaller than 10^6.

Examples for lists with cycles (here, more generally, the lists may extend beyond cycles and may contain multiple, even nested, cycles):

• [0,5,6,1,3,5,6,1,3,8,7,0] --> [5,6,1,3]
• [0,2,4,3,3,3,0,1,6,7] --> [3],[3]
• [2,1,1,3,3,1,1,3,3,4,5] --> [1],[3],[1],[3],[1,1,3,3]
• [7,6,2,3,2,1,7,1,9,1,7,1,9,0,4] --> [1,7,1,9]

Examples for lists with no cycles:

• [0,5,6,3,5,6,1,3,8,7,0]
• [0,2,4,0,1,6,7]
• [2,1,3,4,5]
• [7,6,2,3,2,1,7,1,9,1,7,1,0,4]

What is the fastest (and optionally most elegant/pythonic) way to**

• find if there are cycles, return True or False, and
• optionally: return all cycles, with or without any kind of cycle ordering (e.g. by index of first cycle element in list, then by cycle length)?

标签： pythonlistcycle

Answer 1

这是我能给的最好的。

from math import floor
sample = samples[0]
def find_max_seq(sample):
    max_possible_size_ans = floor(len(sample)/2)
    possible_size_ans = list(range(1,max_possible_size_ans+1))
    max_idx = len(sample)-1
    outs = []
    for size in possible_size_ans:
        last_idx= 0
        start_idx = 0
        while last_idx < max_idx :
            first_pair = sample[start_idx:start_idx+size]
            second_start = start_idx+size
            second_pair = sample[second_start:second_start+size]
            if first_pair == second_pair:
                outs.append(first_pair)
            start_idx +=1
            last_idx = second_start+size
            
    return outs