Сортируемая по стеку перестановка

В математике и информатике — перестановка, сортируемая стеком (также называемая перестановкой дерева ). — это перестановка , элементы которой могут быть отсортированы с помощью алгоритма, внутренняя память которого ограничена одной структурой данных стека . Перестановки, сортируемые стеком, — это именно те перестановки, которые не содержат шаблон перестановки 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 . Более того, он заметил, что если алгоритму не удается отсортировать входные данные, то эти входные данные невозможно отсортировать с помощью одного стека.

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

Биекции и перечисление

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

Ссылки

• Авис, Дэвид ; Новорожденный, Монро (1981), «О поп-стеках в сериях», Utilitas Mathematica , 19 : 129–140, MR   0624050 .
• Бона, Миклош (2002), «Обзор дисциплин сортировки стека» , Электронный журнал комбинаторики , 9 (2): A1, doi : 10.37236/1693 , MR   2028290 .
• Бувель, Матильда; Россин, Доминик; Виалетт, Стефан (2007), «Самый длинный общий разделимый шаблон среди перестановок», Комбинаторное сопоставление шаблонов (CPM 2007) , Конспекты лекций по информатике, том. 4580, Springer, стр. 316–327, doi : 10.1007/978-3-540-73437-6_32 , ISBN.  978-3-540-73436-9 .
• Фельснер, Стефан; Пергель, Мартин (2008), «Сложность сортировки с помощью сетей стеков и очередей», Алгоритмы - ESA 2008 , Конспекты лекций по информатике, том. 5193, Карлсруэ, Германия, стр. 417–429, номер номера : 10.1007/978-3-540-87744-8_35 , ISBN.  978-3-540-87743-1 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
• Нотт, Гэри Д. (февраль 1977 г.), «Система нумерации для бинарных деревьев», Communications of the ACM , 20 (2): 113–115, doi : 10.1145/359423.359434 .
• Кнут, Дональд (1968), «Том 1: Фундаментальные алгоритмы», Искусство компьютерного программирования , Ридинг, Массачусетс: Аддисон-Уэсли .
• Микели, Энн; Россин, Доминик (2006), «Редактирование расстояния между немаркированными упорядоченными деревьями», Theoretical Informatics and Applications , 40 (4): 593–609, arXiv : math/0506538 , doi : 10.1051/ita:2006043 , MR   2277052 , S2CID   2259835 .
• Розенштиль, Пьер ; Тарьян, Роберт Э. (1984), «Коды Гаусса, плоские гамильтоновы графы и перестановки, сортируемые стеком», Journal of Algorithms , 5 (3): 375–390, doi : 10.1016/0196-6774(84)90018-X , МР   0756164
• Ротем, Д. (1981), «Перестановки, сортируемые стеком», Discrete Mathematics , 33 (2): 185–196, doi : 10.1016/0012-365X(81)90165-5 , MR   0599081 .
• Тарьян, Роберт (апрель 1972 г.), «Сортировка с использованием сетей очередей и стеков», Journal of the ACM , 19 (2): 341–346, doi : 10.1145/321694.321704 .