Перестановка с сортировкой по стеку - Stack-sortable permutation

В математика и Информатика, а перестановка с сортировкой по стеку (также называемый перестановка дерева)^[1] это перестановка чьи элементы могут быть отсортированный алгоритмом, внутреннее хранилище которого ограничено одним структура данных стека. Сортированные по стеку перестановки - это именно те перестановки, которые не содержат шаблон перестановки 231; они подсчитаны Каталонские числа, и может быть помещен в биекция со многими другими комбинаторными объектами с той же функцией счета, включая Дайковые тропы и бинарные деревья.

Сортировка стопкой

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

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

Кнут заметил, что этот алгоритм правильно сортирует одни входные последовательности и не может сортировать другие. Например, последовательность 3,2,1 отсортирована правильно: все три элемента помещаются в стек, а затем выталкиваются в порядке 1,2,3. Однако последовательность 2, 3, 1 не отсортирована правильно: алгоритм сначала нажимает 2, а затем выталкивает его, когда видит большее входное значение 3, в результате чего 2 выводится до 1, а не после него.

Поскольку этот алгоритм является сортировка сравнения его успех или неудача не зависят от числовых значений входной последовательности, а только от их относительного порядка; то есть ввод может быть описан перестановка необходимо для формирования этого ввода из отсортированной последовательности той же длины. Кнут охарактеризовал перестановки, которые этот алгоритм правильно сортирует, как перестановки, не содержащие шаблон перестановки 231: три элемента Икс, y, и z, появляющиеся во входных данных в соответствующем порядке, с z < Икс < y. Более того, он заметил, что, если алгоритм не может отсортировать ввод, то этот ввод нельзя отсортировать с помощью одного стека.

Кроме того, что вдохновляет на дальнейшую работу по сортировке с использованием более сложных систем стеков и связанных структур данных,^[2] Исследование Кнута положило начало изучению шаблоны перестановок и классов перестановок, определенных запрещенными шаблонами.

Биекции и подсчет

Последовательность толчков и выталкиваний, выполняемая алгоритмом сортировки Кнута при сортировке перестановок, сортируемых по стеку, формирует Язык Дайка: переинтерпретация push как левой круглой скобки и pop как правой скобки дает строку сбалансированных скобок. Более того, каждая строка Дика получается из перестановки, сортируемой по стеку, и каждые две разные перестановки с сортировкой по стеку производят разные строки Дика. По этой причине количество сортируемых стеком перестановок длины п совпадает с количеством струн Дика длиной 2п, то Каталонский номер

{ displaystyle C_ {n} = { frac {1} {n + 1}} { binom {2n} {n}}.}

^[3]

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

Сортируемые по стеку перестановки также могут быть переведены напрямую в и из (без метки) бинарные деревья, еще один комбинаторный класс чья функция подсчета представляет собой последовательность каталонских чисел. Бинарное дерево может быть преобразовано в перестановку, сортируемую по стеку, путем нумерации его узлов в порядок слева направо, а затем перечислить эти номера в порядке их посещения обход предварительного заказа дерева: сначала корень, затем левое поддерево, затем правое поддерево, продолжение рекурсивно внутри каждого поддерева. В обратном направлении перестановка, сортируемая по стеку, может быть декодирована в дерево, в котором первое значение Икс перестановки соответствует корню дерева, следующая Икс - 1 значения декодируются рекурсивно для получения левого дочернего элемента корня, а остальные значения снова рекурсивно декодируются для получения правого дочернего элемента.^[1]

Несколько других классов перестановок также могут быть помещены в биекцию с сортированными по стеку перестановками. Например, перестановки, которые избегают шаблонов 132, 213 и 312, могут быть сформированы соответственно из сортируемых по стеку (избегающих 231) перестановок путем обращения перестановки, заменяя каждое значение Икс в перестановке п + 1 − Икс, или обе операции вместе. Перестановки, избегающие 312, также являются инверсиями перестановок, избегающих 231, и были названы реализуемые стеком перестановки поскольку они представляют собой перестановки, которые могут быть сформированы из перестановки идентичности последовательностью операций выталкивания из ввода и выталкивания на вывод в стеке.^[4]Так как Кнут (1968) Было отмечено, что перестановки, исключающие 123 и 321, также имеют ту же функцию подсчета, несмотря на то, что они менее напрямую связаны с перестановками, сортируемыми по стеку.

Случайные перестановки с сортировкой по стеку

Ротем (1981) исследует свойства выбранных перестановок, сортируемых по стеку. равномерно случайно среди всех таких перестановок заданной длины. ожидаемая длина из самая длинная убывающая подпоследовательность в такой перестановке ${ displaystyle { sqrt { pi n}} - O (1)}$ , отличающиеся на постоянный коэффициент от неограниченных случайных перестановок (для которых ожидаемая длина приблизительно равна ${ displaystyle 2 { sqrt {n}}}$ ). Ожидаемая длина самой длинной восходящей последовательности еще сильнее отличается от неограниченных перестановок: она равна ${ Displaystyle (п + 1) / 2}$ . Ожидаемое количество значений в перестановке, которые больше, чем все предыдущие значения, составляет только ${ Displaystyle 3–6 / (п + 2)}$ , меньше, чем его логарифмическое значение для неограниченных перестановок. И ожидаемое количество инверсии является ${ Displaystyle Theta (п ^ {3/2})}$ , в отличие от его значения ${ Displaystyle Theta (п ^ {2})}$ для неограниченных перестановок.

Дополнительные свойства

Каждая перестановка определяет граф перестановок, граф, вершинами которого являются элементы перестановки, а ребра соединяют пары элементов, перевернутый по перестановке. Графы перестановок сортированных по стеку перестановок: тривиально идеальный.^[4]

Для каждого элемента я перестановки п, определить б_я быть количеством других элементов, которые находятся слева и больше, чем я. потом п можно сортировать по стеку тогда и только тогда, когда для всех я, б_я − б_я + 1 ≤ 1.^[1]

Алгоритмы

Knott (1977) использует взаимно однозначное соответствие между перестановками, сортируемыми по стеку, и двоичными деревьями для определения числового ранга для каждого двоичного дерева и для построения эффективных алгоритмов для вычисления ранга дерева ("ранжирование") и для вычисления дерева с заданным рангом ("снятие ранга" ").

Мишели и Россин (2006) определены две операции редактирования перестановок: удаление (создание шаблон перестановки ) и его обратное. Используя такое же соответствие между деревьями и перестановками, они заметили, что эти операции соответствуют сжатие края в дереве и его обратное. Применяя полиномиальное время динамическое программирование алгоритм для редактировать расстояние в деревьях они показали, что расстояние редактирования между двумя перестановками, сортируемыми по стеку (а следовательно, и самый длинный общий шаблон), можно найти за полиномиальное время. Позже этот метод был обобщен на алгоритмы поиска наиболее длинных общих паттернов разделимые перестановки;^[5] однако самая длинная проблема общего шаблона - NP-полная для произвольных перестановок.^[6]

Заметки

^ ^а ^б ^c Knott (1977).
^ Тарьян (1972); Avis и новорожденный (1981); Розенштиль и Тарьян (1984); Бона (2002); Фельснер и Пергель (2008). См. Также множество дополнительных ссылок, предоставленных Боной.
^ Кнут (1968); Ротем (1981).
^ ^а ^б Ротем (1981).
^ Бувель, Россин и Виалетт (2007).
^ Мишели и Россин (2006).

использованная литература

Авис, Дэвид; Новорожденный, Монро (1981), «О поп-стеках в сериале», Utilitas Mathematica, 19: 129–140, Г-Н 0624050.
Бона, Миклош (2002), «Обзор дисциплин сортировки стопок», Электронный журнал комбинаторики, 9 (2): A1, Г-Н 2028290.
Бувель, Матильда; Россин, Доминик; Виалетт, Стефан (2007), «Самый длинный общий разделяемый образец среди перестановок», Комбинаторное сопоставление с образцом (CPM 2007), Конспект лекций по информатике, 4580, Springer, стр. 316–327, Дои:10.1007/978-3-540-73437-6_32.
Фельснер, Стефан; Пергель, Мартин (2008), "Сложность сортировки с сетями стеков и очередей", Proc. 16-й евро. Symp. Алгоритмы, Карлсруэ, Германия, стр. 417–429, Дои:10.1007/978-3-540-87744-8_35, ISBN 978-3-540-87743-1.
Кнотт, Гэри Д. (февраль 1977 г.), "Система нумерации бинарных деревьев", Коммуникации ACM, 20 (2): 113–115, Дои:10.1145/359423.359434.
Кнут, Дональд (1968), "Том 1: Основные алгоритмы", Искусство программирования, Ридинг, Массачусетс: Эддисон-Уэсли.
Микели, Энн; Россин, Доминик (2006), «Изменить расстояние между упорядоченными деревьями без меток», Теоретическая информатика и приложения, 40 (4): 593–609, arXiv:математика / 0506538, Дои:10.1051 / ita: 2006043, Г-Н 2277052.
Розенштиль, Пьер; Тарджан, Роберт Э. (1984), "Коды Гаусса, планарные гамильтоновы графы и сортированные по стеку перестановки", Журнал алгоритмов, 5 (3): 375–390, Дои:10.1016 / 0196-6774 (84) 90018-Х, Г-Н 0756164
Ротем, Д. (1981), "Перестановки, сортируемые стеком", Дискретная математика, 33 (2): 185–196, Дои:10.1016 / 0012-365X (81) 90165-5, Г-Н 0599081.
Тарьян, Роберт (Апрель 1972 г.), "Сортировка с использованием сетей очередей и стеков", Журнал ACM, 19 (2): 341–346, Дои:10.1145/321694.321704.

[knott-1] а ^б ^c Knott (1977).

[2] Тарьян (1972); Avis и новорожденный (1981); Розенштиль и Тарьян (1984); Бона (2002); Фельснер и Пергель (2008). См. Также множество дополнительных ссылок, предоставленных Боной.

[3] Кнут (1968); Ротем (1981).

[rotem81-4] а ^б Ротем (1981).

[5] Бувель, Россин и Виалетт (2007).

[6] Мишели и Россин (2006).

[1]

[2]

[3]

[4]

[5]

[6]