Сепарабельная перестановка

Блочное структурирование (транспонированной) матрицы перестановок сепарабельной перестановки (4,5,2,1,3,8,6,7) и соответствующего помеченного двоичного дерева; цвета указывают глубину дерева

В комбинаторной математике сепарабельная перестановка — это перестановка , которую можно получить из тривиальной перестановки 1 с помощью прямых сумм и косых сумм . Разделимые перестановки могут характеризоваться запрещенными шаблонами перестановок 2413 и 3142; они также являются перестановками, чьи графы перестановок являются кографами , и перестановками, которые реализуют последовательно -параллельные частичные порядки . Можно за полиномиальное время проверить , является ли данная разделимая перестановка шаблоном в более крупной перестановке, или найти самый длинный общий подшаблон двух разделимых перестановок.

Определение и характеристика

Большая типичная сепарабельная перестановка

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

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

Как доказывают Бозе, Басс и Любив (1998) , отделимые перестановки также можно охарактеризовать с точки зрения шаблонов перестановок : перестановка является отделимой тогда и только тогда, когда она не содержит ни 2413, ни 3142 в качестве шаблона.

Разделимые перестановки также имеют характеристику из алгебраической геометрии : если набор различных действительных многочленов имеет равные значения в некотором номере x , то перестановка, которая описывает, как численный порядок многочленов изменяется в точке x, является разделимой, и каждая отделимая перестановка может быть разделена. реализоваться таким образом.

Комбинаторное перечисление

Сепарабельные перестановки нумеруются числами Шредера . То есть существует одна отделимая перестановка длины один, две длины два, и вообще количество отделимых перестановок заданной длины (начиная с длины один) равно

1, 2, 6, 22, 90, 394, 1806, 8558, .... (последовательность A006318 в OEIS )

для класса матриц перестановок, эквивалентных разделимым перестановкам Этот результат был доказан Шапиро и Стивенсом (1991) , с использованием канонической формы разделяющего дерева, в котором правый дочерний элемент каждого узла имеет знак, отличный от знака самого узла, а затем применение теории производящих функций к этим деревьям. Другое доказательство, более непосредственно применимое к самим разделимым перестановкам, было дано Уэстом (1995) .

Алгоритмы

Бозе, Басс и Любив (1998) показали, что можно за полиномиальное время определить , является ли данная разделимая перестановка шаблоном в более крупной перестановке, в отличие от той же проблемы для неразделимых перестановок, которая является NP-полной .

Задача поиска самого длинного разделимого шаблона, общего для набора входных перестановок, может быть решена за полиномиальное время для фиксированного числа входных перестановок, но является NP-трудной, когда количество входных перестановок может быть переменным, и остается NP-трудной, когда количество входных перестановок может быть переменным. сложно, даже если все входы сами по себе разделены.

История

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

Шапиро и Стивенс (1991) снова рассмотрели разделимые перестановки в своем исследовании бутстрап-перколяции - процесса, в котором исходная матрица перестановок модифицируется путем многократного изменения на единицу любого матричного коэффициента, который имеет двух или более ортогональных соседей , равных одному. Как они показывают, класс перестановок, которые преобразуются в результате этого процесса в матрицу «все единицы», представляет собой в точности класс разделимых перестановок.

Термин «сепарабельная перестановка» был введен позже Бозе, Бассом и Любивом (1998) , которые рассматривали их из-за их алгоритмических свойств.

Связанные структуры

Отделимая перестановка 43512 и соответствующий ей граф перестановок

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

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

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

Разделимые перестановки включают в себя в качестве особого случая перестановки, сортируемые стеком , которые избегают шаблона 231.

Ссылки

• Акерман, Эяль; Бареке, Гилл; Пинтер, Рон Ю. (2006), «Биекция между перестановками и планами этажей и ее приложения», Discrete Applied Mathematics , 154 (12): 1674–1684, doi : 10.1016/j.dam.2006.03.018 , MR   2233287
• Авис, Дэвид ; Новорожденный, Монро (1981), «О поп-стеках в сериях», Utilitas Mathematica , 19 : 129–140, MR   0624050 .
• Бувель, Матильда; Россин, Доминик; Виалетт, Стефан (2007), «Самый длинный общий разделимый шаблон среди перестановок», Комбинаторное сопоставление шаблонов (CPM 2007) , Конспекты лекций по информатике, том. 4580, Springer, стр. 316–327, номер doi : 10.1007/978-3-540-73437-6_32 , ISBN.  978-3-540-73436-9 .
• Бозе, Просенджит ; Басс, Джонатан; Любив, Анна (1998), «Сопоставление шаблонов для перестановок», Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190(97)00209-3 , MR   1620935 .
• Гис, Этьен (2017), Необычная математическая прогулка , Лион: ENS Éditions, arXiv : 1612.06373 , ISBN  978-2-84788-939-0 , МР   3702027
• Китаев, Сергей (2011), «2.2.5 Разделимые перестановки», Закономерности в перестановках и словах , Монографии по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag , стр. 57–66, doi : 10.1007/978-3-642-17333-2 , ISBN.  978-3-642-17332-5 , Збл   1257.68007 .
• Шапиро, Луи; Стивенс, Артур Б. (1991), «Бутстреп-перколяция, числа Шредера и проблема N -королей», SIAM Journal on Discrete Mathematics , 4 (2): 275–280, doi : 10.1137/0404025 , MR   1093199 .
• Шепенец, А.А.; Оттен, RHJM (1980), «Генеалогический подход к проблеме планировки», 17-я конференция. по автоматизации проектирования (DAC 1980) , стр. 535–542, doi : 10.1145/800139.804582 , ISBN  0-89791-020-6 , S2CID   2031785 .
• Уэст, Джулиан (1995), «Генерация деревьев и чисел Каталана и Шредера», Discrete Mathematics , 146 (1–3): 247–262, doi : 10.1016/0012-365X(94)00067-1 , MR   1360119 .