Алгоритм поиска последовательности чисел, удовлетворяющих множеству условий - PullRequest
Новая
       16

Алгоритм поиска последовательности чисел, удовлетворяющих множеству условий

0 голосов
/ 07 ноября 2018

Задача

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

Правила:

  • N должно быть больше 1

  • Последовательности с менее чем 3 записями должны быть игнорируется

  • Возвращаемые последовательности всегда должны быть максимально возможными для заданное значение N

  • Последовательности всех нулей не учитываются

Мое решение

  1. Перебрать список чисел длины M

  2. На каждой итерации:

    1.a содержит текущий номер и текущий индекс в current_number и current_index соответственно.

    1.b Вычислите максимально возможное количество последовательных числовых последовательностей, в которые может поместиться current_number, и удерживайте это число в nested_iteration_count.

    1.c Запустите вложенную итерацию с числом циклов nested_iteration_count и N при минимально возможном значении N = 2

    1.c.1 Проверьте, существует ли последовательность. Если он существует, сохраните последовательность в массиве

    1.c.2 Увеличьте N на 1 и повторяйте цикл, пока итерации внутреннего цикла не будут завершены.

  3. Повторите внешний цикл для следующего номера

* 1 058 * * Пример 1 059 *

Рассмотрим следующий список целых чисел:

Номер 2 10 4 3 8 6 9 9 18 27

Индекс 0 1 2 3 4 5 6 7 8 9

Найдены следующие последовательности:

  • 2, 4, 8
  • 3, 9, 27

Этот алгоритм, очевидно, имеет O(n^2) сложность. Можно ли улучшить это?

1 Ответ

0 голосов
/ 07 ноября 2018

Быстрая реализация Python с использованием оптимизации @ user3386109

На первом этапе проверяется, продолжается ли прогрессирование с множителем N для i-го элемента

Второй этап - получение самой длинной последовательности для каждого N - может быть сделан более кратким

res содержит самые длинные прогрессии для (N:(count, endingindex) {2: (3, 4), 3: (3, 9)}

import math
lst = [2,10,4,3,8,6,9,9,18,27]
l = len(lst)
mp = {}
mn = min(lst)
mx = max(lst)
nmax = int(math.sqrt(mx / mn))
for i in range(2, l):
    for n in range(2, min(i, (l - 1)//2, nmax) + 1):
        if lst[i - n] * n == lst[i]:
            t = (i-n, n)
            le = mp[t] if t in mp else 1
            mp[(i, n)] = le + 1

res = {}
for x in mp:
    n = x[1]
    le = mp[x]
    ending = x[0]
    if n in res:
        if res[n][0] < le:
            res[n] = (le, ending)
    else:
        res[n] = (le, ending)

print(mp)
print(res)

{(2, 2): 2, (4, 2): 3, (5, 2): 2, (6, 3): 2, (8, 2): 2, (8, 3): 2, (9, 3): 3}
{2: (3, 4), 3: (3, 9)}
...