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

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

Пример

В первых 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

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

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

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

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

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

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

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

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

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

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

Тогда алгоритм действует следующим образом:

P = array of length N
M = array of length N + 1
M[0] = -1 // undefined so can be set to any value

L = 0
for i in range 0 to N-1: //N-1 included
    // Binary search for the smallest positive l ≤ L
    // such that X[M[l]] > X[i]
    lo = 1
    hi = L + 1
    while lo < hi:
        mid = lo + floor((hi-lo)/2) // lo <= mid < hi
        if X[M[mid]] >= X[i]
            hi = mid
        else: // if X[M[mid]] < X[i]
            lo = mid + 1

    // After searching, lo == hi is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
// It consists of the values of X at the L indices:
// ...,  P[P[M[L]]], P[M[L]], M[L]
S = array of length L
k = M[L]
for j in range L-1 to 0: //0 included
    S[j] = X[k]
    k = P[k]

return S

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

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

С использованием `X = [2, 8, 9, 5, 6, 7, 1]`
Значения, хранящиеся в переменных	`X[i]`	`newL`	`P`	`M`	`X[M]`	`L`
До `for i` петля			`P = []`	`M = [-1]`	`X[M] = [N/A]`	`L = 0`
В конце цикла `i = 0`	`X[i] = 2`	`newL = 1`	`P = [-1]`	`M = [-1, 0]`	`X[M] = [N/A, 2]`	`L = 1`
В конце цикла `i = 1`	`X[i] = 8`	`newL = 2`	`P = [-1, 0]`	`M = [-1, 0, 1]`	`X[M] = [N/A, 2, 8]`	`L = 2`
В конце цикла `i = 2`	`X[i] = 9`	`newL = 3`	`P = [-1, 0, 1]`	`M = [-1, 0, 1, 2]`	`X[M] = [N/A, 2, 8, 9]`	`L = 3`
В конце цикла `i = 3`	`X[i] = 5`	`newL = 2`	`P = [-1, 0, 1, 0]`	`M = [-1, 0, 3, 2]`	`X[M] = [N/A, 2, 5, 9]`	`L = 3`
В конце цикла `i = 4`	`X[i] = 6`	`newL = 3`	`P = [-1, 0, 1, 0, 3]`	`M = [-1, 0, 3, 4]`	`X[M] = [N/A, 2, 5, 6]`	`L = 3`
В конце цикла `i = 5`	`X[i] = 7`	`newL = 4`	`P = [-1, 0, 1, 0, 3, 4]`	`M = [-1, 0, 3, 4, 5]`	`X[M] = [N/A, 2, 5, 6, 7]`	`L = 4`
В конце цикла `i = 6`	`X[i] = 1`	`newL = 1`	`P = [-1, 0, 1, 0, 3, 4, -1]`	`M = [-1, 6, 3, 4, 5]`	`X[M] = [N/A, 1, 5, 6, 7]`	`L = 4`
Значения, хранящиеся в переменных	`S`				`k`	`X[k]`
До `for j` петля	`S = [N/A, N/A, N/A, N/A]`				`k = M[4] = 5`	`X[5] = 7`
В конце цикла `j = 3`	`S = [N/A, N/A, N/A, 7]`				`k = P[5] = 4`	`X[4] = 6`
В конце цикла `j = 2`	`S = [N/A, N/A, 6, 7]`				`k = P[4] = 3`	`X[3] = 5`
В конце цикла `j = 1`	`S = [N/A, 5, 6, 7]`				`k = P[3] = 0`	`X[0] = 2`
В конце цикла `j = 0`	`S = [2, 5, 6, 7]`				`k = P[0] = -1`	`X[-1] = N/A`

Ограничения длины

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

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

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

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

См. также

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

Ссылки

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

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

[1] Олдос, Дэвид ; Диаконис, Перси (1999), «Самые длинные возрастающие подпоследовательности: от сортировки по терпению к теореме Байка – Дейфта – Йоханссона», Бюллетень Американского математического общества , 36 (4): 413–432, doi : 10.1090/S0273-0979-99 -00796-X .

[romik-2] Jump up to: ^а ^б Ромик, Дэн (2015). Удивительная математика самых длинных возрастающих подпоследовательностей . дои : 10.1017/CBO9781139872003 . ISBN 9781107075832 .

[schensted-3] Jump up to: ^а ^б Шенстед, К. (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] Голумбик, MC (1980), Алгоритмическая теория графов и совершенные графы , Информатика и прикладная математика, Academic Press, стр. 159 .

[6] Фредман, Майкл Л. (1975), «О вычислении длины самых длинных возрастающих подпоследовательностей», Discrete Mathematics , 11 (1): 29–35, doi : 10.1016/0012-365X(75)90103-X .

[7] Эрдос, Пол ; Секерес, Джордж (1935), «Комбинаторная задача в геометрии» , Compositio Mathematica , 2 : 463–470 .

[8] Стил, Дж. Майкл (1995), «Вариации на тему монотонной последовательности Эрдеша и Секереса», у Олдоса, Дэвида ; Диаконис, Персия ; Спенсер, Джоэл ; и др. (ред.), Дискретная вероятность и алгоритмы (PDF) , Тома IMA по математике и ее приложениям, том. 72, Springer-Verlag, стр. 111–131 .

[vk-9] Вершик, А.М. ; Керов К.В. (1977), "Асимптотика меры Планшераля симметрической группы и предельная форма для таблиц Юнга", Докл. Акад. Наук СССР , 233 : 1024–1027 .

[10] Байк, Джинхо; Дейфт, Перси; Йоханссон, Курт (1999), «О распределении длины самой длинной возрастающей подпоследовательности случайных перестановок», Журнал Американского математического общества , 12 (4): 1119–1178, arXiv : math/9810105 , doi : 10.1090/ S0894-0347-99-00307-0 .

[ss81-11] Сэмюэлс, Стивен. М.; Стил, Дж. Майкл (1981), «Оптимальный последовательный выбор монотонной последовательности из случайной выборки» (PDF) , Annals of Probability , 9 (6): 937–947, doi : 10.1214/aop/1176994265 , в архиве (PDF) ) из оригинала от 30 июля 2018 г.

[ans2015-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). Удивительная математика длиннейших возрастающих подпоследовательностей . Учебники Института математической статистики. Нью-Йорк: Издательство Кембриджского университета. ISBN 978-1-107-42882-9 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]