Самая длинная возрастающая подпоследовательность

Проблема по информатике

В информатике задача о самой длинной возрастающей подпоследовательности направлена ​​на поиск подпоследовательности заданной последовательности , в которой элементы подпоследовательности отсортированы в порядке возрастания и в которой подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Самые длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин, связанных с математикой , включая алгоритмику , теорию случайных матриц , теорию представлений и физику . ^{[1] [2]} Задача о самой длинной возрастающей подпоследовательности разрешима за время , где обозначает длину входной последовательности. ^[3] ${\displaystyle O(n\log n),}$ ${\displaystyle n}$

Пример

В первых 16 членах двоичной последовательности Ван дер Корпута

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

одна из самых длинных возрастающих подпоследовательностей — это

0, 2, 6, 9, 11, 15.

Эта подпоследовательность имеет длину шесть; входная последовательность не имеет семичленных возрастающих подпоследовательностей. Самая длинная возрастающая подпоследовательность в этом примере не является единственным решением: например,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

— другие возрастающие подпоследовательности равной длины в той же входной последовательности.

Связь с другими алгоритмическими проблемами

Задача о самой длинной возрастающей подпоследовательности тесно связана с задачей о самой длинной общей подпоследовательности , которая имеет решение динамического программирования с квадратичным временем : самая длинная возрастающая подпоследовательность последовательности является самой длинной общей подпоследовательностью и где — результат сортировки. Однако для особого случая, когда входные данные представляют собой перестановку целых чисел, этот подход можно сделать гораздо более эффективным, что приведет к временным ограничениям вида ^[4] ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle T,}$ ${\displaystyle T}$ ${\displaystyle S.}$ ${\displaystyle 1,2,\ldots ,n,}$ ${\displaystyle O(n\log \log n).}$

Наибольшая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности перестановки, которая определяет граф (предполагая, что исходная непереставленная последовательность отсортирована от наименьшего значения к наибольшему). Аналогично, максимальный независимый набор в графе перестановок соответствует самой длинной неубывающей подпоследовательности. Поэтому алгоритмы самой длинной возрастающей подпоследовательности могут быть использованы для эффективного решения проблемы клики в графах перестановок. ^[5]

В соответствии Робинсона–Шенстеда между перестановками и таблицами Юнга длина первой строки таблицы, соответствующей перестановке, равна длине самой длинной возрастающей подпоследовательности перестановки, а длина первого столбца равна длине самой длинной убывающей подпоследовательности. ^[3]

Эффективные алгоритмы

Описанный ниже алгоритм эффективно решает задачу самой длинной возрастающей подпоследовательности с массивами и бинарным поиском . Он обрабатывает элементы последовательности по порядку, сохраняя самую длинную возрастающую подпоследовательность, найденную до сих пор. Обозначим значения последовательности как и т. д. Затем после обработки алгоритм сохранит целое число и значения в двух массивах: ${\displaystyle X[0],X[1],\ldots ,}$ ${\displaystyle X[i],}$ ${\displaystyle L}$

• ${\displaystyle L}$— хранит длину самой длинной возрастающей подпоследовательности, найденной на данный момент.
• ${\displaystyle M[l]}$— хранит индекс наименьшего значения, такого, что существует возрастающая подпоследовательность длины, заканчивающаяся на в диапазоне Явно предположим, что обозначает множество всех индексов, таких что и существует возрастающая подпоследовательность длины, заканчивающаяся на Тогда — это индекс в , для которого минимизируется; это означает, что и (или, что эквивалентно, и для каждого ); если несколько индексов удовлетворяют этому условию, то — наибольший из них. ${\displaystyle k}$ ${\displaystyle X[k]}$ ${\displaystyle l}$ ${\displaystyle X[k]}$ ${\displaystyle k\leq i.}$ ${\displaystyle K_{i,l}}$ ${\displaystyle j}$ ${\displaystyle j\leq i}$ ${\displaystyle l}$ ${\displaystyle X[j].}$ ${\displaystyle k=M[l]}$ ${\displaystyle K_{i,l}}$ ${\displaystyle X[M[l]]}$ ${\displaystyle M[l]\in K_{i,l}}$ ${\displaystyle X[M[l]]=\min _{j\in K_{i,l}}X[j]}$ ${\displaystyle M[l]\in K_{i,l}}$ ${\displaystyle j\in K_{i,l},}$ ${\displaystyle X[M[l]]\leq X[j]}$ ${\displaystyle M[l]}$
  • Для ясности, «существует возрастающая подпоследовательность длины, заканчивающаяся на » означает, что существуют индексы, заканчивающиеся на такие, что ${\displaystyle l}$ ${\displaystyle X[k]}$ ${\displaystyle l}$ ${\displaystyle i_{1}<i_{2}<\cdots <i_{l}=k}$ ${\displaystyle k}$ ${\displaystyle X\left[i_{1}\right]<X\left[i_{2}\right]<\cdots <X[k].}$
  • Обратите внимание, что поскольку представляет собой длину возрастающей подпоследовательности, а представляет собой индекс ее окончания. ${\displaystyle 1\leq l\leq i+1,}$ ${\displaystyle l\geq 1}$ ${\displaystyle k\geq 0}$
  • Длина больше длины , но возможно, что не все элементы в этом массиве используются алгоритмом (фактически, если самая длинная возрастающая последовательность имеет длину , то только используются алгоритмом). Однако если используется/определено , то (и более того, при итерации также будет выполнено). не определено, поскольку последовательности длины не имеют конечного индекса ( может быть любым значением). ${\displaystyle M}$ ${\displaystyle 1}$ ${\displaystyle X}$ ${\displaystyle L}$ ${\displaystyle M[1],\ldots ,M[L]}$ ${\displaystyle M[l]}$ ${\displaystyle l-1\leq M[l]}$ ${\displaystyle i,}$ ${\displaystyle M[l]\leq i}$ ${\displaystyle M[0]}$ ${\displaystyle 0}$ ${\displaystyle M[0]}$
• ${\displaystyle P[k]}$— сохраняет индекс предшественника в самой длинной возрастающей подпоследовательности, заканчивающейся на ${\displaystyle X[k]}$ ${\displaystyle X[k].}$
  • Длина равна длине ${\displaystyle P}$ ${\displaystyle X,}$
  • Если тогда while не определено, так как не имеет предшественника ( может быть любым значением). ${\displaystyle k>0}$ ${\displaystyle P[k]<k}$ ${\displaystyle P[0]}$ ${\displaystyle X[0]}$ ${\displaystyle P[0]}$

Поскольку приведенный ниже алгоритм использует нумерацию, начинающуюся с нуля , для ясности он дополнен символом , который остается неиспользованным, так что соответствует подпоследовательности длины Реальная реализация может пропускать и корректировать индексы соответствующим образом. ${\displaystyle M}$ ${\displaystyle M[0],}$ ${\displaystyle M[l]}$ ${\displaystyle l.}$ ${\displaystyle M[0]}$

Обратите внимание, что в любой точке алгоритма последовательность увеличивается. Ведь если есть увеличивающаяся подпоследовательность длины, заканчивающаяся на , то есть и подпоследовательность длины, заканчивающаяся на меньшем значении: а именно та, которая заканчивается на Таким образом, мы можем выполнять бинарный поиск в этой последовательности за логарифмическое время. $${\displaystyle X[M[1]],X[M[2]],\ldots ,X[M[L]]}$$ ${\displaystyle l\geq 2}$ ${\displaystyle X[M[l]],}$ ${\displaystyle l-1}$ ${\displaystyle X[P[M[l]]].}$

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

Демонстрация кода.

P = массив длины NM = массив длины N + 1M[0] = -1 // не определено, поэтому может быть установлено любое значениеЛ = 0для i в диапазоне от 0 до N-1: //N-1 включено // Двоичный поиск наименьшего положительного l ≤ L // такой, что X[M[l]] >= X[i] ло = 1 привет = Л + 1 в то время как ло < привет: мид = ло + пол((хай-ло)/2) // ло <= мид < хи если X[M[mid]] >= X[i] привет = середина иначе : // если X[M[mid]] < X[i] ло = середина + 1 // После поиска lo == hi на 1 больше, чем // длина самого длинного префикса X[i] новыйL = ло // Предшественник X[i] — это последний индекс // подпоследовательность длины newL-1 P[i] = M[newL-1] M[newL] = i  если новыйL > L: // Если мы нашли подпоследовательность длиннее любой из // пока не найдено, обновите L L = новыйL// Реконструируем самую длинную возрастающую подпоследовательность// Он состоит из значений X в индексах L:// ..., П[П[М[Л]]], П[М[Л]], М[Л]S = массив длины Lк = М[Л]для j в диапазоне от L-1 до 0: //0 включено S[j] = X[k] к = Р[к]возврат S

Поскольку алгоритм выполняет один бинарный поиск на элемент последовательности, его общее время может быть выражено с использованием нотации Big O , как Фредман (1975) обсуждает вариант этого алгоритма, который он приписывает Дональду Кнуту ; в варианте, который он изучает, алгоритм проверяет, может ли каждое значение быть использовано для расширения текущей самой длинной возрастающей последовательности, за постоянное время, перед выполнением бинарного поиска. С этой модификацией алгоритм использует максимум сравнений в худшем случае, что является оптимальным для алгоритма, основанного на сравнении, вплоть до постоянного множителя в термине . ^[6] ${\displaystyle O(n\log n).}$ ${\displaystyle X[i]}$ ${\displaystyle n\log _{2}n-n\log _{2}\log _{2}n+O(n)}$ ${\displaystyle O(n)}$

Пример запуска

Границы длины

Согласно теореме Эрдеша–Секереша , любая последовательность различных целых чисел имеет возрастающую или убывающую подпоследовательность длины ^{[7] [8]} Для входных данных, в которых каждая перестановка входных данных равновероятна, ожидаемая длина самой длинной возрастающей подпоследовательности приблизительно равна ^{[9] [2]} ${\displaystyle n^{2}+1}$ ${\displaystyle n+1.}$ ${\displaystyle 2{\sqrt {n}}.}$

В пределе, когда стремится к бесконечности, теорема Бейка-Дейфта-Йоханссона гласит, что длина самой длинной возрастающей подпоследовательности случайно переставленных элементов имеет распределение, приближающееся к распределению Трейси-Уидома , распределению наибольшего собственного значения случайной матрицы в гауссовском унитарном ансамбле . ^[10] ${\displaystyle n}$ ${\displaystyle n}$

Онлайн алгоритмы

Самая длинная возрастающая подпоследовательность также изучалась в условиях онлайн-алгоритмов , в которых элементы последовательности независимых случайных величин с непрерывным распределением — или, альтернативно, элементы случайной перестановки — по одному представляются алгоритму, который должен решить, включать или исключать каждый элемент, без знания более поздних элементов. В этом варианте задачи, который допускает интересные приложения в нескольких контекстах, можно разработать оптимальную процедуру выбора, которая, учитывая случайную выборку размера в качестве входных данных, будет генерировать возрастающую последовательность с максимальной ожидаемой длиной размера приблизительно ^[11] Длина возрастающей подпоследовательности, выбранной этой оптимальной процедурой, имеет дисперсию приблизительно равную , а ее предельное распределение является асимптотически нормальным после обычного центрирования и масштабирования. ^[12] Те же асимптотические результаты справедливы с более точными границами для соответствующей задачи в условиях пуассоновского процесса прибытия. ^[13] Дальнейшее уточнение в установке процесса Пуассона дается посредством доказательства центральной предельной теоремы для оптимального процесса выбора, которая выполняется, с подходящей нормализацией, в более полном смысле, чем можно было бы ожидать. Доказательство дает не только «правильную» функциональную предельную теорему, но и (сингулярную) ковариационную матрицу трехмерного процесса, суммирующую все взаимодействующие процессы. ^[14] ${\displaystyle F}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {2n}}.}$ ${\displaystyle {\sqrt {2n}}/3,}$

Смотрите также

• Анатолий Вершик  – русский математик (1933–2024), который изучал приложения теории групп к длиннейшим возрастающим подпоследовательностям в случайных перестановках. ^[15]
• Самая длинная чередующаяся подпоследовательность
• Самая длинная общая подпоследовательность  – Алгоритмическая задача на парах последовательностей
• Сортировка терпения  – Алгоритм сортировки – эффективный метод нахождения длины самой длинной возрастающей подпоследовательности.
• Пластический моноид  – моноид положительных целых чисел по модулю эквивалентности Кнута Pages displaying wikidata descriptions as a fallback– алгебраическая система, определяемая преобразованиями, которые сохраняют длину самой длинной возрастающей подпоследовательности.

Ссылки

1. Олдос, Дэвид ; Диаконис, Перси (1999), «Самые длинные возрастающие подпоследовательности: от терпеливой сортировки до теоремы Байка–Дейфта–Йоханссона», Бюллетень Американского математического общества , 36 (4): 413–432, doi : 10.1090/S0273-0979-99-00796-X.
2. Romik, Dan (2015). Удивительная математика длиннейших возрастающих подпоследовательностей . doi :10.1017/CBO9781139872003. ISBN 9781107075832.
3. Schensted, C. (1961), «Самые длинные возрастающие и убывающие подпоследовательности», Canadian Journal of Mathematics , 13 : 179–191, doi : 10.4153/CJM-1961-015-3 , MR  0121305.
4. Хант, Дж.; Шимански, Т. (1977), «Быстрый алгоритм вычисления длиннейших общих подпоследовательностей», Communications of the ACM , 20 (5): 350–353, doi : 10.1145/359581.359603 , S2CID  3226080.
5. Golumbic, MC (1980), Алгоритмическая теория графов и совершенные графы , Computer Science and Applied Mathematics, Academic Press, стр. 159.
6. Фредман, Майкл Л. (1975), «О вычислении длины самых длинных возрастающих подпоследовательностей», Дискретная математика , 11 (1): 29–35, doi : 10.1016/0012-365X(75)90103-X.
7. Эрдеш, Пол ; Секерес, Джордж (1935), «Комбинаторная проблема в геометрии», Compositio Mathematica , 2 : 463–470..
8. Стил, Дж. Майкл (1995), «Вариации на тему монотонной подпоследовательности Эрдёша и Секереша», в Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (ред.), Discrete Probability and Algorithms (PDF) , IMA Volumes in Mathematics and its Applications, т. 72, Springer-Verlag, стр. 111–131.
9. Вершик, А. М .; Керов, К. В. (1977), "Асимптотика планхерной меры симметрической группы и предельная форма для таблиц Юнга", Докл. АН СССР , 233 : 1024–1027.
10. Байк, Джинхо; Дейфт, Перси; Йоханссон, Курт (1999), «О распределении длины самой длинной возрастающей подпоследовательности случайных перестановок», Журнал Американского математического общества , 12 (4): 1119–1178, arXiv : math/9810105 , doi : 10.1090/S0894-0347-99-00307-0.
11. Сэмюэлс, Стивен М.; Стил, Дж. Майкл (1981), «Оптимальный последовательный выбор монотонной последовательности из случайной выборки» (PDF) , Annals of Probability , 9 (6): 937–947, doi : 10.1214/aop/1176994265 , архивировано (PDF) из оригинала 30 июля 2018 г.
12. Арлотто, Алессандро; Нгуен, Винь В.; Стил, Дж. Майкл (2015), «Оптимальный онлайн-выбор монотонной подпоследовательности: центральная предельная теорема», Стохастические процессы и их приложения , 125 (9): 3596–3622, arXiv : 1408.6750 , doi : 10.1016/j.spa.2015.03.009, S2CID  15900488
13. Брусс, Ф. Томас ; Дельбаен, Фредди (2001), «Оптимальные правила последовательного выбора монотонных подпоследовательностей максимальной ожидаемой длины», Стохастические процессы и их приложения , 96 (2): 313–342, doi : 10.1016/S0304-4149(01)00122-3.
14. Брусс, Ф. Томас ; Дельбаен, Фредди (2004), «Центральная предельная теорема для оптимального процесса выбора монотонных подпоследовательностей максимальной ожидаемой длины», Стохастические процессы и их приложения , 114 (2): 287–311, doi : 10.1016/j.spa.2004.09.002.
15. Ромик, Дэн (2015). Удивительная математика длиннейших возрастающих подпоследовательностей . Учебники Института математической статистики. Нью-Йорк: Cambridge University Press. ISBN 978-1-107-42882-9.

Внешние ссылки

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