Учитывая поток случайных чисел, попробуйте найти числа, которые расположены равномерно

Question

Проблема:

У меня есть поток чисел, которые не равномерно распределены в качестве входных данных, и мне нужно найти последовательность чисел, используя приведенную выше, которая возвращает максимально возможное число для первой последовательности, но равномерно распределенных.

Пример:

stream = [1,4,9,11,12,17,18,25,30,33,34,41,44,49,57,65,73,81,89,90,97,100]

Мне нужно найти последовательность, которая содержит как можно больше чисел, равномерно разделенных

Например, я знаю, что могу найти:

1,9,17,25,33,41,49,57,65,75,81,89,97

все они разделены на 8.

Как мне решить эту проблему в целом?

Answer 1

def find_seq(lst):
    running = []
    done = []
    so_far = []
    for element in sorted(lst):
        still_running = []
        for run in running:
            d, m = divmod(element - run[0], run[2])
            if m == 0:
                if d == run[1]:
                    run[1] += 1
                    still_running.append(run)
                else:
                    done.append(run)
            else:
                still_running.append(run)
        running = still_running + [[previous, 2, element - previous] for previous in so_far]
        so_far.append(element)
    return max(done + running, key=lambda run: run[1])

start, length, step = find_seq([1,4,9,11,12,17,18,25,30,33,34,41,44,49,57,65,73,81,89,90,97,100])

Для каждой пары элементов мы предполагаем, что они начинают последовательность (с предполагаемой длины 2 для начала).Для любого нового элемента мы проверяем, соответствует ли он последовательности (или более), которую мы отслеживаем;если это так, но значение было пропущено, последовательность заканчивается;в противном случае мы увеличиваем длину последовательности.Все последовательности будут заканчиваться в конце ввода.Тогда легко понять, какая последовательность побежала дольше всего.