Входные данные и результат работы.
На вход алгоритма подаётся перестановка натуральных чисел от 1 до n. Результатом работы является пара таблиц Юнга одинаковой формы: записывающая (P) и нумерующая (Q).
Пример:
Дана перестановка размера 20:
В результате работы алгоритма будет получена следующая пара таблиц Юнга одинаковой формы размера 20:
Описание алгоритма.
Для построения пары таблиц P и Q, последовательно обрабатываются n элементов перестановки \phi=\{\phi_1, \phi_2, \ldots, \phi_n\}.
Для таблицы P:
Изначально таблица P пустая.
1) \phi_1 помещается в таблицу P.
2) Элементы \phi_i = 2\ldots n помещаются в таблицу следующим образом:
Если \phi_i больше всех значений в столбце, то сверху столбца добавляется клетка с \phi_i (форма таблицы изменяется).
Иначе \phi_i записывается на место ближайшего большего числа, которое “выталкивается” в столбец справа. Вытолкнутое значение помещается в следующий столбец по тому же принципу.
3) Обработка элемента \phi_i заканчивается после изменения формы таблицы P.
Для таблицы Q:
Изначально таблица Q пустая.
1) При обработке очередного элемента перестановки выполняется серия последовательных перемещений значений, записанных в таблицу P, в результате которых форма таблицы изменяется – это происходит в ячейке, помещенной сверху какого-либо столбца.
2) К таблице Q добавляется ячейка с теми же координатами: таким образом, формы таблиц совпадают. В данную ячейку записывается индекс обработанного элемента перестановки.
Таблица Q нумерует ячейки в порядке изменения формы таблицы P.
Пример построения пары таблиц для перестановки длины 6:
Светло-голубым обозначен путь, по которому проходит очередной элемент до расширения формы таблиц, а синим – конец пути и место расширения.
Ниже приведен пример работы алгоритма RSK.
Теорема: Алгоритм RSK задаёт взаимно однозначное соответствие между перестановками и парами таблиц Юнга.
При этом случайным равномерно распределенным перестановкам соответствуют таблицы с планшерелевским распределением.
Обратное преобразование RSK.
В силу биективности алгоритма RSK, по паре таблиц Юнга одинаковой формы возможно восстановить исходную перестановку. Такая процедура называется алгоритмом обратного преобразования RSK, который состоит в выполнении шагов прямого алгоритма RSK в обратном порядке:
- Клетка с максимальным числом в таблице Q соответствует последнему расширению формы таблиц.
- Данная клетка удаляется из таблиц P и Q (значение из таблицы P сохраняется в буфер).
- В столбце слева (в предыдущем столбце) таблицы P ищется наибольший элемент, не превосходящий сохранённый в буфере.
- Буфер и найденная ячейка меняются местами.
Пункты 3 и 4 повторяются, пока не будет достигнут первый столбец. Удалённое из первого столбца значение записывается в последовательность. Запись значений буфера в последовательность происходит справа налево.
В качестве примера рассмотрим пару таблиц Юнга, полученную в ходе применения алгоритма RSK в предыдущем разделе:
Светло-голубым обозначен путь, по которому проходит очередной элемент до расширения формы таблиц, а синим – конец пути и место расширения формы таблицы.
Как видно из примера, в самом деле была получена та же перестановка, что и в предыдущем пункте, до применения преобразования RSK.
Более подробный пример приведён на видео ниже.
Алгоритм RSK и вещественные числа.
На вход алгоритма RSK возможно также подавать последовательности вещественных чисел, например из диапазона [0, 1]. В таком случае будут получены полустандартная таблица P и стандартная таблица Q.
Заметим, что по этим таблицам может быть восстановлена исходная последовательность, поскольку для проведения обратного преобразования достаточно, чтобы стандартной таблицей была Q.
Алгоритм RSK применим также для обработки бесконечных входных последовательностей.
Перестановки и обратные перестановки.
Обратной перестановкой \pi^{-1} называется перестановка, в которой числа из перестановки \pi меняются местами с их порядковыми номерами.
Например, перестановка \pi_2 является обратной по отношению к перестановке \pi_1:
\pi_1 = \{3, 8, 5, 10, 9, 4, 6, 1, 7, 2\}
\pi_2 = \{8, 10, 1, 6, 3, 7, 9, 2, 5, 4\}
При этом выполняется следующее соотношение: \pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=\epsilon, где \epsilon – тождественная перестановка (числа равны порядковым номерам).
Теорема симметрии. Если перестановке \pi соответствует пара таблиц P, Q, то обратной перестановке \pi^{-1} соответствуют таблицы Q, P.
Преобразования Кнута.
Преобразование Кнута преобразует одну перестановку в другую, соответствуя одному из нескольких типов, указанных ниже (a < b < c), остальные элементы остаются на месте.
Таким образом, каждое преобразование Кнута меняет местами два соседних элемента a и c при условии, что рядом с a или с расположен элемент b, удовлетворяющий условию (a < b < c).
Эквивалентность и двойственная эквивалентность по Кнуту.
Две перестановки называются эквивалентными по Кнуту если одна из них может быть получена из другой при помощи последовательных преобразований Кнута
Преобразование RSK также позволяет задать два отношения эквивалентности на множестве перестановок – эквивалентность по Кнуту и двойственную эквивалентность по Кнуту.
Теорема. Две перестановки эквивалентны по Кнуту, если их таблицы P совпадают. Ниже представлен пример трёх перестановок, принадлежащих одному классу эквивалентности по Кнуту, и соответствующих им пар таблиц.
Теорема. Две перестановки двойственно эквивалентны по Кнуту, если их таблицы Q совпадают. Пример трёх перестановок, двойственно эквивалентных по Кнуту, приведён на рисунке ниже.
Классы эквивалентности по Кнуту.
Ниже приведён пример 16 перестановок, образующих класс эквивалентности по Кнуту, причём перестановки, которые могут быть получены друг из друга одним преобразованием Кнута, соединены ребром.
Важно отметить, что это не единственный существующий класс эквивалентности, и для перестановок различного размера их будет различное количество, очевидно, равное размерности диаграммы Юнга соответствующей формы.
Теорема Шенстеда.
В любой перестановке могут быть выделены возрастающие подпоследовательности, в которых каждый последующий элемент больше предыдущего, а также убывающие подпоследовательности, в которых каждый последующий элемент меньше предыдущего.
Ниже представлены некоторые возрастающие и убывающие подпоследовательности для перестановки размера 20:
Теорема. Рассмотрим перестановку чисел от 1 до n, а также соответствующую ей пару таблиц Юнга P и Q формы \lambda=\{\lambda_1, \lambda_2, …, \lambda_k\}, где \lambda_i – высота i-го столбца, k – ширина первой строки.
- Высота первого столбца \lambda_1 таблиц P, Q равна длине наибольшей возрастающей подпоследовательности a_{max} в соответствующей перестановке.
- Ширина первой строки k таблиц P, Q равна длине наибольшей убывающей подпоследовательности d_{max} в соответствующей перестановке.
Ниже приведена пара таблиц, соответствующих перестановке 13, 2, 16, 4, 7, 9, 12, 1, 3, 20, 11, 6, 18, 14, 5, 19, 17, 10, 8, 15, представленной на предыдущем рисунке.
Как видно из изображения, высота первого столбца равна максимальной длине возрастающей подпоследовательности (7) а ширина таблицы – максимальной длине убывающей (5).
Доказательство теоремы Шенстеда.
Введем понятие простых подпоследовательностей.
i-я простая подпоследовательность (basic subsequence) – хронологически упорядоченная последовательность чисел, занимающих клетку в строке i первого столбца таблицы P во время работы алгоритма RSK.
Очевидно, что каждая простая подпоследовательность убывающая, так как число может быть вытолкнуто в соседний столбец только меньшим числом.
Поскольку каждая простая подпоследовательность убывает, возрастающая подпоследовательность может включать в себя не более одного члена каждой простой подпоследовательности, а значит искомая длина наибольшей возрастающей подпоследовательности a_{max} не превосходит высоты первого столбца: a_{max}\leq\lambda_1.
При этом для каждого члена j-й (j > 1) простой подпоследовательности r найдется член j-1-й простой подпоследовательности, строго меньший r. Это объясняется тем, что когда элемент j-й подпоследовательности попадает в первый столбец, под ним обязательно будет находиться какой-либо меньший элемент. Соответственно, если начать с \lambda_1-й простой подпоследовательности, то можно построить возрастающую последовательность длины \lambda_1 (последовательность строится справа налево!), из чего вытекает, что a_{max} = \lambda_1.
Пути выталкиваний.
Для изучения эволюции значений таблицы P в алгоритме RSK удобно рассматривать так называемые пути выталкиваний.
Путь выталкиваний – это последовательность клеток таблицы P, перемещающихся в ходе одной итерации преобразования RSK. На изображении ниже изображены пути выталкиваний для таблицы размера 10.
В пути выталкивания i-я клетка соединена ссылкой с i + 1-oй клеткой.
Деревья выталкиваний.
Дерево выталкиваний – множество путей выталкиваний, сходящихся в одну клетку.
Лес выталкиваний.
Лес выталкиваний – объединение всех путей выталкиваний таблицы P.
Один из возможных вариантов программной реализации преобразования RSK состоит в поддержании структуры леса выталкиваний. В таком случае очередной элемент последовательности будет перемещаться по соответствующему дереву и в итоге будет вытолкнут в корень этого дерева. При таком подходе задача сводится к поиску изменений в структуре леса выталкиваний, поскольку при движении по ней значений будут меняться и ссылки, которые необходимо корректировать. При этом ссылки будут меняться лишь в небольшой окрестности дерева, по которому перемещается очередной элемент.
Предельная форма путей выталкиваний.
В статье [Romik, Sniady’14] было доказано, что путь выталкиваний с ростом размера таблицы будет стремиться к своей предельной форме. Ниже приведён пример формы таблицы размера 10^8, в которой выделены некоторые пути выталкиваний.
Предельную форму двумерной таблицы, получаемой при помощи алгоритма RSK, можно изобразить в трёхмерном пространстве, где значения по оси x и y соответствуют нормированным координатам клетки, по оси z – значению в соответствующей клетке с координатами x и y. Нормировка координат происходит посредством деления их на корень из n, где n – размер таблицы.
Красная линия при этом является кривой Вершика-Керова. Благодаря такому методу изображения таблицы возможно в целом оценить рост значений элементов в таблице в зависимости от координат в ней, не привязываясь к конкретным значениям.
Открытые проблемы.
Для изучения асимптотических свойств таблиц Юнга сверхбольших размеров (состоящих из миллионов клеток) необходима эффективная программная реализация алгоритма RSK.
Существуют различные подходы для реализации алгоритма. Стандартный алгоритм предполагает последовательный поиск ближайших больших к выталкиваемому элементов в столбцах. Также существует подход, основанный на поддержании структуры леса выталкиваний. При организации алгоритма RSK через лес выталкиваний отпадает задача поиска ближайшего большего элемента в следующем столбце так как путь выталкивания, по которому пройдут элементы, уже вычислен. Однако, в таком случае, при прохождении элемента по пути необходимо корректировать ссылки в путях выталкиваний для сохранения корректности структуры таблицы.
Открытой проблемой является разработка иных, более эффективных, реализаций алгоритма RSK.
Также исследовательский интерес вызывает дальнейшее изучение асимптотических свойств леса выталкиваний.