Блог

Главная - Вопросы по программированию - Учитывая поток случайных чисел, попытайтесь найти равномерно распределенные числа

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

#python #arrays #numbers

#python #массивы #числа

Вопрос:

Проблема:

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

Пример:

 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.

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

Комментарии:

1. @Taegyung: Этот вопрос предполагает подпоследовательность (непрерывный ряд чисел); в этом вопросе есть промежуточные элементы.

2. Это поток (как в бесконечном источнике) или просто конечная последовательность (как в списке или одномерном массиве)? Если это бесконечный источник, и если числа действительно случайны, существует бесконечное количество ответов — вы сможете найти равномерно распределенные последовательности любого возможного размера шага. С другой стороны, если это просто конечный список, тот факт, что числа являются «случайными», вероятно, становится неактуальным для вашего требования.

3. Из его примера мне кажется довольно ясным, о чем он говорит. Я ожидаю, что под «случайным» он подразумевает «произвольный».

Ответ №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 для начала). Для любого нового элемента мы проверяем, поместится ли он в последовательность (или больше), которую мы отслеживаем; если это так, но значение было пропущено, последовательность завершена; в противном случае мы увеличиваем длину последовательности. Все последовательности завершатся в конце ввода. Тогда легко увидеть, какая последовательность выполнялась дольше всего.