Вопрос по arrays, language-agnostic, algorithm, repetition, sequence – Нахождение повторяющейся последовательности в конце последовательности чисел

5

Моя проблема заключается в следующем: у меня большая последовательность чисел. Я знаю, что после некоторого момента он становится периодическим, то есть в начале последовательности есть k чисел, а затем еще m чисел, которые повторяются для остальной части последовательности. В качестве примера, чтобы сделать это более понятным, последовательность может выглядеть следующим образом: [1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3 , ...], где k равно 5 и m равно 4, а повторяющийся блок равен [2, 1, 1, 3]. Как ясно из этого примера, у меня могут быть повторяющиеся биты внутри большего блока, так что это не помогает просто искать первые экземпляры повторения.

Однако я не знаю, что такое k или m - моя цель - взять последовательность [a_1, a_2, ..., a_n] в качестве входных данных и вывести последовательность [a_1, ..., a_k, [a_ (k) +1), ..., a_ (k + m)]] - в основном усекает более длинную последовательность, перечисляя большую ее часть как повторяющийся блок.

Есть ли эффективный способ решить эту проблему? Кроме того, вероятно, сложнее, но более идеально в вычислительном отношении - возможно ли это сделать, когда я генерирую соответствующую последовательность, так что мне нужно генерировать минимальное количество? Я рассмотрел другие похожие вопросы на этом сайте, но все они, похоже, имеют дело с последовательностями без начального неповторяющегося бита и часто без необходимости беспокоиться о внутреннем повторении.

Если это поможет / будет полезно, я также могу понять, почему я смотрю на это и для чего я буду его использовать.

Спасибо!

РЕДАКТИРОВАТЬ: Во-первых, я должен был упомянуть, что я не знаю, заканчивается ли входная последовательность точно в конце повторяющегося блока.

Реальная проблема, над которой я пытаюсь работать, - это написание красивого выражения в замкнутой форме для продолжения разложений дробей (CFE) квадратичных иррациональных чисел (фактически, отрицательных CFE). Очень просто сгенерировать частичные коэффициенты * для этих ДОВСЕ с любой степенью точности - однако в какой-то момент хвост ДОВСЕ для квадратичного иррационального становится повторяющимся блоком. Мне нужно работать с частными частными в этом повторяющемся блоке.

Мои нынешние мысли таковы: возможно, я смогу адаптировать некоторые предложенные алгоритмы, которые работают с правами на работу с одной из этих последовательностей. В качестве альтернативы, возможно, есть что-то в доказательстве того, почему квадратичные иррациональные числа являются периодическими, что поможет мне понять, почему они начинают повторяться, что поможет мне придумать несколько простых критериев для проверки.

* Если я пишу продолжение расширения дроби как [a_0, a_1, ...], я называю a_i частными частными.

Некоторая справочная информация может быть найдена здесь для заинтересованных:http://en.wikipedia.org/wiki/Periodic_continued_fraction

@Dougal У меня есть некоторые верхние границы для m, хотя они не являются особенно хорошими оценками - последовательность технически бесконечна, но я смотрел на подачу в ее конечной части, которая гарантированно будет иметь многократные повторения повторяющейся части. Который, я полагаю, отвечает на вопрос Алекса - да, у меня гарантированно будет по крайней мере два повторения. Istarion
Если ваша последовательность бесконечна, эта проблема, в общем-то, не разрешима: вы никогда не узнаете, являетесь ли вы просто «внутренним повторением»; сегмент, который остановится в некоторый момент позже. Есть ли у вас какие-либо ограничения наk/m или вы просто хотите получить "лучшее предположение"? Алгоритм, который работает по пути (для раздела «как вы генерируете»)? Dougal
Вы гарантированно имеете по крайней мере 2 повторения последней периодической подпоследовательности в конце данного ввода [a_1 ... a_n]? Alexey Frunze

Ваш Ответ

5   ответов
1

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

И наоборот, если у вас есть строка, где a [x] = a [x + k] для большого числа x, то у вас также есть a [x] = a [x + k] = a [x + 2k] = a [x + 3k] ... поэтому строка, которая соответствует себе при скольжении на небольшое расстояние по сравнению с его длиной, должна содержать повторы.

Если вы посмотрите наhttp://en.wikipedia.org/wiki/Suffix_array, вы увидите, что вы можете построить список всех суффиксов строки в отсортированном порядке, в линейном времени, а также массив, который сообщает вам, сколько символов у каждого суффикса общего с предыдущим суффиксом в отсортированном порядке. Если вы ищите запись с наибольшим значением этого, это будет моим кандидатом для строки, идущей ..1234123412341234, и расстояние между начальными точками двух суффиксов скажет вам длину, с которой повторяется последовательность. (но на практике поиск по хэшу вродеhttp://en.wikipedia.org/wiki/Rabin-Karp может быть быстрее и проще, хотя существуют вполне кодируемые алгоритмы линейного суффиксного линейного времени, например & quot; Простое построение линейного суффиксного массива & quot; Карккайнен и Сандерс).

Предположим, что вы применяете этот алгоритм, когда количество доступных символов составляет 8, 16, 32, 64, .... 2 ^ n, и вы, наконец, найдете повтор в 2 ^ p. Сколько времени вы потратили на ранних стадиях? 2 ^ (p-1) + 2 ^ (p-2) + ..., что составляет около 2 ^ p, поэтому повторные поиски - это только постоянные издержки.

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

Эта страница перечисляет несколько хороших алгоритмов обнаружения цикла и дает реализацию алгоритма на C.

Эти алгоритмы (например, Флойд и тот, который указан в списке) неприменимы, поскольку они работают только на графиках с указателями или в списке, где каждое число зависит только от предыдущего числа.
Алгоритм обнаружения цикла, примененный «из коробки»; будет иметь ложные тревоги повсюду. Однако, если вы увеличиваете размер алфавита, рассматривая каждый кусок из k цифр как одно число или каждое скользящее окно из k цифр как одно число, это может быть полезно для некоторых последовательностей и может быть довольно быстрым.
7

rolling hash для достижения линейной временной сложности и O (1) пространственной сложности (я думаю, что это так, поскольку я не верю, что вы можете иметь бесконечную повторяющуюся последовательность с двумя частотами, которые не кратны друг другу).

Алгоритм: вы просто сохраняете два скользящих хеша, которые расширяются следующим образом:

                       _______  _______  _______
                      /       \/       \/       \
...2038975623895769874883301010883301010883301010
                      .        .        .      ||
                      .        .        .    [][]
                      .        .        .  [ ][ ]
                      .        .        .[  ][  ]
                      .        .       [.  ][   ]
                      .        .     [  . ][    ]
                      .        .   [    .][     ]
                      .        . [      ][      ]
                      .        [       ][       ]

Продолжайте делать это для всей последовательности. Первый проход будет обнаруживать только повторы, повторенные 2 * n раз для некоторого значения n. Однако это не наша цель: наша цель в первом проходе - обнаружить все возможные периоды, что и происходит. По мере выполнения последовательности, выполняющей этот процесс, мы также отслеживаем все относительно простые периоды, которые нам нужно будет проверить позже:

periods = Set(int)
periodsToFurthestReach = Map(int -> int)

for hash1,hash2 in expandedPairOfRollingHashes(sequence):
    L = hash.length
    if hash1==hash2:
        if L is not a multiple of any period:
            periods.add(L)
            periodsToFurthestReach[L] = 2*L
        else L is a multiple of some periods:
            for all periods P for which L is a multiple:
                periodsToFurthestReach[P] = 2*L

После этого процесса у нас есть список всех периодов и того, как далеко они достигли. Наш ответ, вероятно, самый дальний, но мы проверяем все другие периоды на повторение (быстро, потому что мы знаем периоды, на которые мы проверяем). Если это трудно с вычислительной точки зрения, мы можем оптимизировать, удаляя периоды (которые перестают повторяться), когда мы проходим по списку, очень похоже на сито Эратосфена, сохраняя приоритетную очередь, когда мы в следующий раз ожидаем, что период будет повторяться.

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

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

@Istarion: если вы не заканчивали на границе повторяющегося блока, вы все равно обнаружите ту же повторяющуюся последовательность (тот же период), но можете прикрепить часть повторяющегося блока, например, например. ... 4697123 (45123) (45123) ... Чтобы адаптироваться, возьмите каждое решение, предложенное вышеупомянутым методом, и попытайтесь "сдвинуть" повторяющиеся блоки потенциального решения слева, цифра за цифрой, по сравнению с (например) 3 = seq [-1], 2 = seq [-2], 1 = seq [-3], 7! = seq [-4] - & gt; сдвиг на 3.
Это выглядит супер полезно - спасибо! К сожалению, я не могу гарантировать, что мы закончим нашу последовательность в конце повторяющегося блока, но кажется вероятным, что идеи здесь могут быть адаптированы для работы в любом случае. Istarion
1

does a_n == a_n-1 does (a_n,a_n-1) == (a_n-2,a_n-3) ...

Это явно O (m ^ 2). Кажется, единственной доступной границей является то, что m & lt; n / 2, так что это O (n ^ 2)

Это приемлемо для вашего приложения? (Мы делаем вашу домашнюю работу для вас, или здесь есть реальная проблема?)

К сожалению, я не могу гарантировать, что наш ввод заканчивается в конце повторяющейся последовательности, но, возможно, мы все еще можем работать справа. Проблема реального мира, над которой я работаю, включает в себя непрерывные расширения дробей (в частности, отрицательные расширения непрерывных дробей). Квадратичные числа являются периодическими в их продолженном расширении дроби (но не обязательно чисто периодическом, отсюда и начальная часть последовательности), и я хочу иметь возможность написать хороший, замкнутый список, который представляет собой всю совокупность отрицательного расширения непрерывной дроби заданное квадратичное число. Istarion
2

ninjagecko дал хороший рабочий ответ на вопрос, который я поставил. Спасибо большое! Тем не менее, я закончил тем, что нашел более эффективный, математически обоснованный способ выполнения конкретного случая, который я рассматриваю, - то есть выписал выражение в замкнутой форме для продолжения разложения дроби квадратичного иррационального. Очевидно, что это решение будет работать только для этого конкретного случая, а не общего случая, о котором я спрашивал, но я подумал, что было бы полезно поставить его здесь на тот случай, если у других возникнет аналогичный вопрос.

По сути, я вспомнил, что квадратичное иррациональное число сокращается тогда и только тогда, когда его непрерывное расширение дроби является чисто периодическим, то есть оно повторяется с самого начала, без каких-либо ведущих членов.

Когда вы отрабатываете продолжение числа дробей числа x, вы в основном устанавливаете x_0 равным x, а затем формируете свою последовательность [a_0; a_1, a_2, a_3, ...] путем определения a_n = floor (x_n) и x_ (n + 1) = 1 / (x_n - a_n). Обычно вы просто продолжаете это, пока не достигнете желаемой точности. Однако для наших целей мы просто запускаем этот метод до тех пор, пока x_k не будет уменьшенным квадратичным иррациональным числом (что происходит, если оно больше 1 и его сопряжение находится между -1 и 0). Как только это произойдет, мы знаем, что a_k - это первый член нашего повторяющегося блока. Затем, когда мы находим x_ (k + m + 1) равным x_k, мы знаем, что a_ (k + m) - это последний член в нашем повторяющемся блоке.

Похожие вопросы