Oddzielna permutacja
W matematyce kombinatorycznej permutacja rozdzielna to permutacja , którą można uzyskać z trywialnej permutacji 1 za pomocą sum bezpośrednich i sum skośnych . Rozdzielne permutacje mogą być scharakteryzowane przez zabronione wzorce permutacji 2413 i 3142; są to również permutacje, których wykresy permutacyjne są kografami , oraz permutacje realizujące szeregowo -równoległe rzędy częściowe . Możliwe jest testowanie w czasie wielomianowym czy dana rozdzielna permutacja jest wzorcem w większej permutacji, czy też znaleźć najdłuższy wspólny podwzorzec dwóch rozdzielnych permutacji.
Definicja i charakterystyka
Bose, Buss i Lubiw (1998) definiują permutację rozdzielną jako permutację, która ma drzewo rozdzielające : zakorzenione drzewo binarne , w którym elementy permutacji pojawiają się (w kolejności permutacji) na liściach drzewa i w którym potomkowie każdego węzła drzewa tworzą ciągły podzbiór tych elementów. Każdy wewnętrzny węzeł drzewa jest albo węzłem dodatnim, w którym wszyscy potomkowie lewego dziecka są mniejsi niż wszyscy potomkowie prawego węzła, albo węzłem ujemnym, w którym wszyscy potomkowie lewego węzła są więksi niż wszyscy potomkowie prawego węzła . Dla danej permutacji może istnieć więcej niż jedno drzewo: jeśli dwa sąsiednie węzły w tym samym drzewie mają ten sam znak, to można je zastąpić inną parą węzłów za pomocą obracania drzewa .
Każde poddrzewo rozdzielającego drzewa może być interpretowane jako samo reprezentujące mniejszą permutację rozdzielną, której wartości elementów są określone przez kształt i wzór znaku poddrzewa. Drzewo jednowęzłowe reprezentuje trywialną permutację, drzewo, którego węzeł główny jest dodatni, reprezentuje bezpośrednią sumę permutacji podanych przez jego dwa poddrzewa potomne, a drzewo, którego węzeł główny jest ujemny, reprezentuje sumę skośną permutacji podanych przez jego dwoje dzieci poddrzewa. W ten sposób drzewo rozdzielające jest równoważne konstrukcji permutacji za pomocą sum bezpośrednich i skośnych, zaczynając od trywialnej permutacji.
Jak dowodzą Bose, Buss i Lubiw (1998) , permutacje rozdzielne można również scharakteryzować za pomocą wzorców permutacji : permutacja jest rozdzielna wtedy i tylko wtedy, gdy nie zawiera ani 2413, ani 3142 jako wzorca.
Rozłączne permutacje mają również charakterystykę z geometrii algebraicznej : jeśli zbiór różnych rzeczywistych wielomianów ma równe wartości przy pewnej liczbie x , to permutacja opisująca, w jaki sposób numeryczne uporządkowanie wielomianów zmienia się w x , jest rozdzielna i każda rozdzielna permutacja może zrealizować w ten sposób.
Wyliczanie kombinatoryczne
Rozłączne permutacje są wyliczane przez liczby Schrödera . Oznacza to, że istnieje jedna rozdzielna permutacja o długości jeden, dwie o długości dwa, a ogólnie liczba rozdzielnych permutacji o danej długości (zaczynając od długości jeden) wynosi
Wynik ten został udowodniony dla klasy macierzy permutacji równoważnych permutacjom rozdzielnym Shapiro i Stephensa (1991) , przy użyciu kanonicznej postaci drzewa rozdzielającego, w którym prawy element potomny każdego węzła ma inny znak niż sam węzeł, a następnie zastosowanie teorii funkcji generujących do tych drzew. Inny dowód odnoszący się bardziej bezpośrednio do permutacji rozdzielnych został podany przez Westa (1995) .
Algorytmy
Bose, Buss i Lubiw (1998) wykazali, że możliwe jest określenie w czasie wielomianowym , czy dana permutacja rozdzielna jest wzorcem w większej permutacji, w przeciwieństwie do tego samego problemu dla permutacji nierozdzielnych, które są NP-zupełne .
Problem znalezienia najdłuższego możliwego do rozdzielenia wzorca, który jest wspólny dla zbioru permutacji wejściowych, można rozwiązać w czasie wielomianowym dla ustalonej liczby permutacji wejściowych, ale jest NP-trudny, gdy liczba permutacji wejściowych może być zmienna i pozostaje NP- trudne, nawet jeśli wszystkie wejścia są rozdzielne.
Historia
Permutacje rozdzielne pojawiły się po raz pierwszy w pracy Avisa i Newborna (1981) , którzy wykazali, że są to właśnie permutacje, które można sortować według dowolnej liczby stosów pop w szeregach, gdzie stos pop to ograniczona forma stosu w która każda operacja pop wyskakuje ze wszystkich elementów naraz.
Shapiro i Stephens (1991) ponownie rozważyli separowalne permutacje w swoich badaniach perkolacji bootstrap , procesu, w którym początkowa macierz permutacji jest modyfikowana przez wielokrotne zmienianie na jeden dowolnego współczynnika macierzy, który ma dwóch lub więcej ortogonalnych sąsiadów równych jeden. Jak pokazują, klasa permutacji, które są przekształcane w tym procesie w macierz wszystkiego jednego, jest dokładnie klasą permutacji rozdzielnych.
Termin „rozdzielna permutacja” został wprowadzony później przez Bose, Buss i Lubiw (1998) , którzy rozważali je ze względu na ich właściwości algorytmiczne.
Powiązane struktury
Każdą permutację można wykorzystać do zdefiniowania grafu permutacyjnego , grafu, którego wierzchołki są elementami permutacji, a krawędzie są odwrotnościami permutacji . W przypadku permutacji rozdzielnej strukturę tego grafu można odczytać z drzewa separacji permutacji: dwa wierzchołki grafu sąsiadują ze sobą wtedy i tylko wtedy, gdy ich najniższy wspólny przodek w drzewie separacji jest ujemny . Grafy, które można w ten sposób utworzyć z drzew, nazywane są kografami (skrót od grafów redukowalnych dopełniacza), a drzewa, z których są utworzone, nazywane są cotrees. Zatem rozdzielne permutacje są dokładnie tymi permutacjami, których wykresy permutacyjne są kografami. Zakazana charakterystyka kografów (są to grafy bez ścieżki indukowanej czterema wierzchołkami ) odpowiada dwóm czteroelementowym zabronionym wzorcom permutacji rozdzielnych.
Rozłączne permutacje są również ściśle związane z szeregowo-równoległymi rzędami częściowymi , częściowo uporządkowanymi zbiorami , których wykresy porównywalności są kografami. Podobnie jak w przypadku kografów i permutacji rozdzielnych, szeregowo-równoległe rzędy częściowe można również scharakteryzować czteroelementowymi zakazanymi podrzędami. Każda permutacja definiuje porządek częściowy, którego wymiar porządku wynosi dwa, w którym elementy do uporządkowania są elementami permutacji i w którym x ≤ y ilekroć x ma mniejszą wartość liczbową niż y i zostaje z niego w permutacji. Permutacje, dla których ten porządek częściowy jest szeregowo-równoległy, są dokładnie permutacjami rozdzielnymi.
Rozłączne permutacje mogą być również używane do opisywania hierarchicznych podziałów prostokątów na mniejsze prostokąty (tak zwane „plany pięter z przekrojami”, używane na przykład w projektowaniu układów scalonych ) za pomocą dodatnich i ujemnych znaków rozdzielającego drzewa do opisania poziomego i pionowego plasterki prostokąta na mniejsze prostokąty.
Oddzielne permutacje obejmują jako szczególny przypadek permutacje z możliwością sortowania stosu , które unikają wzorca 231.
Notatki
- Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), „Bijekcja między permutacjami a planami pięter i jej zastosowania”, Discrete Applied Mathematics , 154 (12): 1674–1684, doi : 10.1016 / j.dam.2006.03.018 , MR 2233287
- Awis, Dawid ; Newborn, Monroe (1981), „Na pop-stosach w seriach”, Utilitas Mathematica , 19 : 129–140, MR 0624050 .
- Bouvel, Matylda; Rossin, Dominik; Vialette, Stéphane (2007), „Najdłuższy wspólny rozdzielny wzór wśród permutacji”, Kombinatoryczne dopasowywanie wzorców (CPM 2007) , Notatki z wykładów z informatyki, tom. 4580, Springer, s. 316–327, doi : 10.1007/978-3-540-73437-6_32 , ISBN 978-3-540-73436-9 .
- Bose, Prosenjit ; Buss, Jonathan; Lubiw, Anna (1998), „Dopasowywanie wzorców dla permutacji”, Information Processing Letters , 65 (5): 277–283, doi : 10.1016/S0020-0190 (97) 00209-3 , MR 1620935 .
- Ghys, Étienne (2017), Pojedyncza promenada matematyczna , Lyon: ENS Éditions, arXiv : 1612.06373 , ISBN 978-2-84788-939-0 , MR 3702027
- Kitaev, Sergey (2011), „2.2.5 Oddzielne permutacje”, Wzorce w permutacjach i słowach , Monografie w informatyce teoretycznej. Seria EATCS, Berlin: Springer-Verlag , s. 57–66, doi : 10.1007/978-3-642-17333-2 , ISBN 978-3-642-17332-5 , Zbl 1257.68007 .
- Szapiro, Ludwik; Stephens, Arthur B. (1991), „Bootstrap perkolacja, liczby Schrödera i N -królów” , SIAM Journal on Discrete Mathematics , 4 (2): 275–280, doi : 10,1137/0404025 , MR 1093199 .
- Szepieniec, AA; Otten, RHJM (1980), „Genealogiczne podejście do problemu układu”, 17 Konf. w sprawie automatyzacji projektowania (DAC 1980) , s. 535–542, doi : 10.1145/800139.804582 , S2CID 2031785 .
- Zachód, Julian (1995), „Generowanie drzew i liczb katalońskich i Schrödera”, Matematyka dyskretna , 146 (1–3): 247–262, doi : 10.1016/0012-365X (94) 00067-1 , MR 1360119 .