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

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

Определение и характеристика [ править ]

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

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

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

Как доказывают Bose, Buss & Lubiw (1998) , отделимые перестановки также могут быть охарактеризованы в терминах паттернов перестановок : перестановка отделима тогда и только тогда, когда она не содержит ни 2413, ни 3142 как паттерн. [2]

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

Комбинаторное перечисление [ править ]

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

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

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

Алгоритмы [ править ]

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

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

История [ править ]

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

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

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

Связанные структуры [ править ]

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

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

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

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

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

Заметки [ править ]

  1. ↑ Китаев (2011) , с. 57.
  2. ^ a b Bose, Buss & Lubiw (1998) ; Китаев (2011) , теорема 2.2.36, с. стр.58.
  3. ^ Ghys (2016) , стр. 15.
  4. ^ См. Китаев (2011) , теорема 2.2.45, стр. 60.
  5. ^ Bouvel, Rossin & Vialette (2007) .
  6. ^ Bose, Buss & Lubiw (1998) .
  7. ^ Szepieniec & Оттена (1980) ; Акерман, Барекет и Пинтер (2006)

Ссылки [ править ]

  • Акерман, Эяль; Барекет, Гилл; Пинтер, Рон Ю. (2006), "взаимно однозначное соответствие между перестановками и, планы этажей и его применения", Дискретный прикладной математики , 154 (12): 1674-1684, DOI : 10.1016 / j.dam.2006.03.018 , МР  2233287
  • Авис, Дэвид ; Новорожденный, Монро (1981), «О серийных стопках», Utilitas Mathematica , 19 : 129–140, MR  0624050.
  • Бувель, Матильда; Россин, Доминик; Vialette, Stéphane (2007), "Наибольшая общая разъемные картина среди перестановок", комбинаторной Pattern Matching (CPM 2007) , Lecture Notes в области компьютерных наук, 4580 , Springer, С. 316-327,. DOI : 10.1007 / 978-3-540- 73437-6_32 , ISBN 978-3-540-73436-9.
  • Бозе, Просенджит ; Басс, Джонатан; Lubiw, Анна (1998), "соответствующий шаблон для перестановок", Information Processing Letters , 65 (5): 277-283, CiteSeerX  10.1.1.39.3641 , DOI : 10.1016 / S0020-0190 (97) 00209-3 , МР  1620935.
  • Гиз, Этьен (2016), A Singular Mathematical Promenade , arXiv : 1612.06373 , Bibcode : 2016arXiv161206373G.
  • Китаев, Сергей (2011), «2.2.5 Разделимые перестановки», Паттерны в перестановках и словах , Монографии по теоретической информатике. Серия EATCS, Берлин: Springer-Verlag , стр. 57–66, DOI : 10.1007 / 978-3-642-17333-2 , ISBN 978-3-642-17332-5, Zbl  1257,68007.
  • Шапиро, Луи; Stephens, Arthur B. (1991), "Бутстрап перколяции, число Schröder, и N -kings проблема", SIAM журнал по дискретной математике , 4 (2): 275-280, DOI : 10,1137 / 0404025 , МР  1093199.
  • Szepieniec, AA; Оттен, RHJM (1980), "Генеалогический подход к проблеме размещения", 17-я конференция. на автоматизации проектирования (DAC 1980) , С. 535-542,. DOI : 10,1109 / DAC.1980.1585298 (неактивный 2021-01-11)CS1 maint: DOI неактивен с января 2021 г. ( ссылка ).
  • Запад, Джулиан (1995), "Генерация дерева и число каталонского и Шрёдер", Дискретная математика , 146 (1-3): 247-262, DOI : 10.1016 / 0012-365X (94) 00067-1 , MR  1360119.