Отделимая перестановка - Separable permutation - Wikipedia

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

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

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

Типичная большая разделимая перестановка

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

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

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

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

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

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

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

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

Алгоритмы

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

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

История

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ Китаев (2011), п. 57.
  2. ^ а б Бозе, Басс и Любив (1998); Китаев (2011), Теорема 2.2.36, с. стр.58.
  3. ^ Гиз (2016), п. 15.
  4. ^ Видеть Китаев (2011), Теорема 2.2.45, с. 60.
  5. ^ Бувель, Россин и Виалетт (2007).
  6. ^ Бозе, Басс и Любив (1998).
  7. ^ Szepieniec & Otten (1980); Акерман, Барекет и Пинтер (2006)

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

  • Акерман, Эяль; Барекет, Гилл; Пинтер, Рон Ю. (2006), "Взаимное соответствие между перестановками и поэтажными планами и его приложениями", Дискретная прикладная математика, 154 (12): 1674–1684, Дои:10.1016 / j.dam.2006.03.018, МИСТЕР  2233287
  • Авис, Дэвид; Новорожденный, Монро (1981), «О поп-стеках в сериале», Utilitas Mathematica, 19: 129–140, МИСТЕР  0624050.
  • Бувель, Матильда; Россин, Доминик; Виалетт, Стефан (2007), «Самый длинный общий разделяемый образец среди перестановок», Комбинаторное сопоставление с образцом (CPM 2007), Конспект лекций по информатике, 4580, Springer, стр. 316–327, Дои:10.1007/978-3-540-73437-6_32, ISBN  978-3-540-73436-9.
  • Бозе, Просенджит; Басс, Джонатан; Любив, Анна (1998), "Сопоставление с образцом для перестановок", Письма об обработке информации, 65 (5): 277–283, CiteSeerX  10.1.1.39.3641, Дои:10.1016 / S0020-0190 (97) 00209-3, МИСТЕР  1620935.
  • Гиз, Этьен (2016), Необычный математический променад, arXiv:1612.06373, Bibcode:2016arXiv161206373G.
  • Китаев, Сергей (2011), «2.2.5 Разделимые перестановки», Паттерны в перестановках и словах, Монографии по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag, стр. 57–66, Дои:10.1007/978-3-642-17333-2, ISBN  978-3-642-17332-5, Zbl  1257.68007.
  • Шапиро, Луи; Стивенс, Артур Б. (1991), "Перколяция бутстрапа, числа Шредера и N-проблема королей ", Журнал SIAM по дискретной математике, 4 (2): 275–280, Дои:10.1137/0404025, МИСТЕР  1093199.
  • Szepieniec, A. A .; Оттен, Р. Х. Дж. М. (1980), "Генеалогический подход к проблеме расположения", 17-я конф. по автоматизации проектирования (DAC 1980), стр. 535–542, Дои:10.1109 / DAC.1980.1585298 (неактивно 09.09.2020)CS1 maint: DOI неактивен по состоянию на сентябрь 2020 г. (связь).
  • Уэст, Джулиан (1995), «Генерация деревьев и числа Каталонии и Шредера», Дискретная математика, 146 (1–3): 247–262, Дои:10.1016 / 0012-365X (94) 00067-1, МИСТЕР  1360119.