Перестановка, сортируемая стеком - Stack-sortable permutation

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

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

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

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

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

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

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

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

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

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

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

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

Несколько других классов перестановок также могут быть помещены в биекцию с перестановками, сортируемыми по стеку. Например, перестановки, которые избегают шаблонов 132, 213 и 312, могут быть сформированы соответственно из сортируемых по стеку (избегающих 231) перестановок путем обращения перестановки, замены каждого значения x в перестановке на n  + 1 -  x , или обе операции вместе взятые. Перестановки, избегающие 312, также являются инверсиями перестановок, избегающих 231, и были названы перестановками, реализуемыми стеком, поскольку они представляют собой перестановки, которые могут быть сформированы из тождественной перестановки последовательностью push-from-input и pop- операции вывода на стек. Как заметил Кнут (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})}$

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

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

Для каждого элемента i перестановки p определите b _i как количество других элементов, которые находятся слева от i и превышают его . Тогда р является стек-сортируемым тогда и только тогда, когда для всех I , б _I  -  б _{я  + 1}  ≤ 1.

Алгоритмы

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

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

Заметки

Рекомендации

• Авис, Дэвид ; Новорожденный, Монро (1981), «О серийных стопках», Utilitas Mathematica , 19 : 129–140, MR  0624050.
• Бона, Миклош (2002), "Обзор дисциплин сортировки стека" , Электронный журнал комбинаторики , 9 (2): A1, MR  2028290.
• Бувель, Матильда; Россин, Доминик; Vialette, Stéphane (2007), "Наибольшая общая разъемные картина среди перестановок", комбинаторной Pattern Matching (CPM 2007) , Lecture Notes в области компьютерных наук, 4580 , Springer, С. 316-327,. DOI : 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.
• Нотт, Gary D. (февраль 1977), "Нумерация система для бинарных деревьев", коммуникаций АСМ , 20 (2): 113-115, DOI : 10,1145 / 359423,359434.
• Кнут, Дональд (1968), "Том 1: Фундаментальные алгоритмы", Искусство компьютерного программирования , чтение, Массачусетс: Аддисон-Уэсли.
• Микели, Энн; Россин, Доминик (2006), «Изменить расстояние между упорядоченными деревьями без меток », Теоретическая информатика и приложения , 40 (4): 593–609, arXiv : math / 0506538 , doi : 10.1051 / ita: 2006043 , MR  2277052.
• Розенштиль, Пьер ; Тарьян, Роберт Э. (1984), «Коды Гаусса, плоские гамильтоновы графы и перестановки, сортируемые по стеку», Журнал алгоритмов , 5 (3): 375–390, DOI : 10.1016 / 0196-6774 (84) 90018-X , Руководство по ремонту  0756164
• Ротем, Д. (1981), "Перестановки, сортируемые стеком", Дискретная математика , 33 (2): 185–196, DOI : 10.1016 / 0012-365X (81) 90165-5 , MR  0599081.
• Тарьян, Роберт (апрель 1972), "Сортировка использования сетей очередей и стеков", Журнал ACM , 19 (2): 341-346, DOI : 10,1145 / 321694,321704.