Inwersja (matematyka dyskretna)

Permutacja z zaznaczoną jedną z jej inwersji. Inwersję można oznaczyć parą miejsc (2, 4) lub parą elementów (5, 2). Odwrotności tej permutacji przy użyciu notacji opartej na elementach to: (3, 1), (3, 2), (5, 1), (5, 2) i (5,4).

W informatyce i matematyce dyskretnej inwersja w sekwencji to para elementów, które nie znajdują się w ich naturalnym porządku .

Definicje

Inwersja

Niech będzie permutacją . $_$ π ${\ displaystyle \ pi}$ między ja $\ displaystyle i}$ i ${\ displaystyle j}$ , jeśli $\ displaystyle i <j}$$\pi (i)>\pi (j)}$ i ${\$ displaystyle . Inwersja jest wskazywana przez uporządkowaną parę zawierającą albo miejsca ${\ Displaystyle (i, j)}$ lub elementy ${\ Displaystyle {\ bigl (} \ pi (i), \ pi (j) {\ bigr )}}$ .

Zbiór inwersji to zbiór wszystkich inwersji. Zestaw inwersji permutacji przy użyciu notacji opartej na miejscu jest taki sam, jak odwrotnej permutacji przy użyciu notacji opartej na elementach, z wymienionymi dwoma składnikami każdej uporządkowanej pary. Podobnie zestaw inwersji permutacji przy użyciu notacji opartej na elementach jest taki sam, jak zestaw inwersji odwrotnej permutacji przy użyciu notacji opartej na miejscu z wymienionymi dwoma składnikami każdej uporządkowanej pary.

$są zwykle definiowane dla permutacji, ale można$ również definiować dla sekwencji: Niech będzie sekwencją (lub permutacją wielozbiorową ). ja ${\ Displaystyle i <j}$ S $\ Displaystyle S (i)> S (j)}$ , albo para miejsc ${\ Displaystyle (i) ,j)}$ lub parę elementów ${\ Displaystyle {\ bigl (} S (i), S (j) {\ bigr)}}$ nazywa się odwróceniem ${\ displaystyle S}$ .

W przypadku sekwencji inwersje zgodnie z definicją opartą na elementach nie są unikalne, ponieważ różne pary miejsc mogą mieć tę samą parę wartości.

Numer inwersji

Liczba inwersji $sekwencji$$Displaystyle X = \$ , , to liczność zbioru inwersji. Jest to powszechna miara uporządkowania (czasami nazywana wstępnym sortowaniem) permutacji lub sekwencji. Liczba inwersji wynosi od 0 do ${\ Displaystyle {\ Frac {n (n-1)} {2}}}$ włącznie. Permutacja i jej odwrotność mają ten sam numer inwersji.

Na przykład ${\ Displaystyle {\ mathtt {inv}} (\ langle 1,2, \ kropki, n \ rangle) = 0},$ ponieważ sekwencja jest uporządkowana. Ponadto, gdy ${\ Displaystyle n=2m}$ jest parzyste, $}$${\ Displaystyle {\ mathtt {inv}} (\ langle m + 1, m + 2, \ kropki, 2 m, 1,2, \ kropki, m \ rangle) =$$_$ para _ Ten ostatni przykład pokazuje, że zbiór, który jest intuicyjnie „prawie posortowany”, może nadal mieć kwadratową liczbę inwersji.

Liczba inwersji to liczba przecięć na diagramie strzałkowym permutacji, odległość tau Kendalla permutacji od permutacji tożsamości oraz suma każdego z wektorów związanych z inwersją zdefiniowanych poniżej.

Inne miary sortowania obejmują minimalną liczbę elementów, które można usunąć z sekwencji, aby uzyskać w pełni posortowaną sekwencję, liczbę i długości posortowanych „przebiegów” w sekwencji, regułę Spearmana (suma odległości każdego elementu od jego posortowanych pozycji) oraz najmniejsza liczba wymian potrzebnych do posortowania sekwencji. Standardowe sortowania porównawczego można dostosować do obliczania liczby inwersji w czasie O( n log n ) .

Wektory związane z inwersją

W użyciu są trzy podobne wektory, które kondensują inwersje permutacji w wektor, który jednoznacznie ją określa. Nazywa się je często wektorem inwersji lub kodem Lehmera . (Lista źródeł znajduje się tutaj .)

W tym artykule użyto terminu wektor inwersji ( $)$ jak Wolfram . Pozostałe dwa wektory są czasami nazywane lewym i prawym wektorem inwersji , ale aby uniknąć pomyłki z wektorem inwersji, w tym artykule nazywa się je licznikiem lewej inwersji ( $)$ i $)$ licznikiem ( . Interpretowane jako liczba silni lewy licznik inwersji daje permutacje odwrotne colexicographic, a prawy licznik inwersji daje indeks leksykograficzny.

Diagram Rotha

Wektor inwersji $z$ { definicją opartą $displaystyle i}$ elementach $jest$ liczbą inwersji, których ) składnikiem jest \ .

${\ Displaystyle v (i)}$ to liczba elementów w ${\ displaystyle \ pi}$ większa niż ${\ displaystyle i}$ przed ${\ displaystyle i}$ .

${\ Displaystyle v (i) ~ ~ = ~ ~ \ # \ {k \ mid k> i ~ \ ziemia ~ \ pi ^ {-1} (k) <\ pi ^ {-1} (i) \}}$

$:$ lewej inwersji z definicją opartą na miejscu jest liczbą inwersji, których większym (prawym) składnikiem jest $l ($$}$ .

${\ Displaystyle l (i)}$ to liczba elementów w ${\ Displaystyle \ pi}$ większa niż ${\ Displaystyle \ pi (i)}$ przed ${\ Displaystyle \ pi (i)}$ .

${\ Displaystyle l (i) ~ ~ = ~ ~ \ # \ lewo \ {k \ środkowy k <i ~ \ ziemia ~ \ pi (k)> \ pi (i) \ prawo \}}$

${\ displaystyle r}$ liczba inwersji , często nazywana kodem Lehmera : z definicją opartą na miejscu jest liczbą inwersji, których mniejszy ( $lewy$ ) składnik to r ( $}$${\ displaystyle r$ .

${\ Displaystyle r (i)}$ to liczba elementów mniejszych niż $Displaystyle$$\ pi (i)}$ po $Displaystyle \ pi (i)}$ .

${\ Displaystyle r (i) ~ ~ = ~ ~ \ # \ {k \ mid k> i ~ \ ziemia ~ \ pi (k) <\ pi (i) \}}$

Zarówno ${\ displaystyle v},$$jak$ i można znaleźć za pomocą diagramu Rothe'a , który jest macierzą permutacji jedynkami reprezentowanymi przez kropki i inwersją (często reprezentowaną przez krzyż) w każdej pozycji. który ma kropkę po prawej stronie i pod nią. ${\ Displaystyle r (i)}$ jest sumą inwersji w rzędzie $}$ Rothe'a, podczas gdy ${\ Displaystyle v (i)$ jest sumą inwersji w kolumnie ${\ displaystyle i}$ . Macierzą $odwrotnością$ odwrotności jest transpozycja, dlatego $permutacja$ jej i odwrotnie.

Przykład: Wszystkie permutacje czterech elementów

Sześć możliwych inwersji 4-elementowej permutacji

Poniższa tabela z możliwością sortowania przedstawia 24 permutacje czterech elementów (w $w$ ) z ich zestawami inwersji opartymi na miejscach (w kolumnie pb), wektorami związanymi z inwersją ( $,$${\ displaystyle l}$ i ${\ displaystyle r}$ kolumny) oraz liczby inwersji (w kolumnie #). (Kolumny z mniejszą czcionką i bez nagłówka są odzwierciedleniem kolumn obok nich i można ich użyć do sortowania ich w porządku koleksykograficznym ).

Można zauważyć, że $i$$zawsze$ mają same cyfry i że $oba$ są $powiązane$ zbiorem inwersji opartym na Nietrywialne elementy $r$ sumy malejących przekątnych pokazanego trójkąta i tych z $\ displaystyle r}$ są sumami rosnących przekątnych. (Pary na malejących przekątnych mają wspólne prawe elementy 2, 3, 4, podczas gdy pary na rosnących przekątnych mają wspólne lewe elementy 1, 2, 3).

Domyślna kolejność tabeli to odwrotna kolejność colex według $displaystyle$ która jest taka sama jak kolejność colex według $l}$ . Porządek Lex według $taki$ sam jak porządek lex według ${\ displaystyle r}$ .

Dla porównania permutacje 3-elementowe
0 1 2 3 4 5 ${\ Displaystyle \ pi}$ ${\ displaystyle v}$ ${\ displaystyle l}$ pb ${\ displaystyle r}$ # 0 123 321 000 000 000 000 000 000 0 1 213 312 100 001 010 010 100 001 1 2 132 231 010 010 100 001 010 010 1 3 312 213 110 011 110 011 200 002 2 4 231 132 200 002 200 002 110 011 2 5 321 123 210 012 210 012 210 012 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

${\ Displaystyle \ pi}$ ${\ displaystyle v}$ ${\ displaystyle l}$ pb ${\ displaystyle r}$ # 0 1234 4321 0000 0000 0000 0000 0000 0000 0 1 2134 4312 1000 0001 0010 0100 1000 0001 1 2 1324 4231 0100 0010 0100 0010 0100 0010 1 3 3124 4213 1100 0011 0110 0110 2000 0002 2 4 2314 4132 2000 0002 0200 0020 1100 0011 2 5 3214 4123 2100 0012 0210 0120 2100 0012 3 6 1243 3421 0010 0100 1000 0001 0010 0100 1 7 2143 3412 1010 0101 1010 0101 1010 0101 2 8 1423 3241 0110 0110 1100 0011 0200 0020 2 9 4123 3214 1110 0111 1110 0111 3000 0003 3 10 2413 3142 2010 0102 1200 0021 1200 0021 3 11 4213 3124 2110 0112 1210 0121 3100 0013 4 12 1342 2431 0200 0020 2000 0002 0110 0110 2 13 3142 2413 1200 0021 2010 0102 2010 0102 3 14 1432 2341 0210 0120 2100 0012 0210 0120 3 15 4132 2314 1210 0121 2110 0112 3010 0103 4 16 3412 2143 2200 0022 2200 0022 2200 0022 4 17 4312 2134 2210 0122 2210 0122 3200 0023 5 18 2341 1432 3000 0003 3000 0003 1110 0111 3 19 3241 1423 3100 0013 3010 0103 2110 0112 4 20 2431 1342 3010 0103 3100 0013 1210 0121 4 21 4231 1324 3110 0113 3110 0113 3110 0113 5 22 3421 1243 3200 0023 3200 0023 2210 0122 5 23 4321 1234 3210 0123 3210 0123 3210 0123 6

Słaba kolejność permutacji

Permutoedr grupy symetrycznej S ₄

Zbiorowi permutacji na n elementach można nadać strukturę częściowego porządku , zwanego słabym rzędem permutacji , który tworzy siatkę .

Diagram Hassego zbiorów inwersji uporządkowanych przez relację podzbioru tworzy szkielet permutoedru .

Jeśli permutacja jest przypisana do każdego zestawu inwersji przy użyciu definicji opartej na miejscu, wynikowa kolejność permutacji jest taka, jak permutoedr, gdzie krawędź odpowiada zamianie dwóch elementów z kolejnymi wartościami. Jest to słaba kolejność permutacji. Tożsamość jest jej minimum, a permutacja utworzona przez odwrócenie tożsamości jest jej maksimum.

Gdyby permutacja została przypisana do każdego zestawu inwersji przy użyciu definicji opartej na elementach, wynikowa kolejność permutacji byłaby taka, jak na wykresie Cayleya, gdzie krawędź odpowiada zamianie dwóch elementów w kolejnych miejscach. Ten wykres Cayleya grupy symetrycznej jest podobny do jego permutoedru, ale z każdą permutacją zastąpioną jej odwrotnością.

Zobacz też

• System liczb czynnikowych
• Wykres permutacji
• Transpozycje, transpozycje proste, inwersje i sortowanie
• Odległość Damerau-Levenshteina
• Parzystość permutacji

Sekwencje w OEIS :

• Sekwencje związane z reprezentacją bazy czynnikowej
• Liczby silni: A007623 i A108731
• Numery inwersji: A034968
• Zestawy inwersyjne skończonych permutacji interpretowane jako liczby binarne: A211362 (powiązana permutacja: A211363 )
• Skończone permutacje, które mają tylko 0 i 1 w swoich wektorach inwersji: A059590 (ich zestawy inwersji: A211364 )
• Liczba permutacji n elementów z k inwersjami; Liczby mahońskie: A008302 (ich maksima w rzędach; liczby Kendalla-Manna: A000140 )
• Liczba połączonych grafów oznaczonych z n krawędziami i n węzłami: A057500

Bibliografia źródłowa

•   Aigner, Martin (2007). „Reprezentacja słowa”. Kurs liczenia . Berlin, Nowy Jork: Springer. ISBN 978-3642072536 .
• Barth, Wilhelm; Mutzel, Petra (2004). „Proste i wydajne dwuwarstwowe liczenie krzyżowe” . Dziennik algorytmów i aplikacji grafów . 8 (2): 179–194. doi : 10.7155/jgaa.00088 .
•   Bona, Miklós (2012). „2.2 Inwersje w permutacjach multisetów”. Kombinatoryka permutacji . Boca Raton, Floryda: CRC Press. ISBN 978-1439850510 .
•   Comtet, Louis (1974). „6.4 Inwersje permutacji [n]”. Zaawansowana kombinatoryka; sztuka skończonych i nieskończonych ekspansji . Dordrecht, Boston: Pub D. Reidel. Co ISBN 9027704414 .
•   Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Wprowadzenie do algorytmów (wyd. 2). MIT Press i McGraw-Hill. ISBN 0-262-53196-8 .
•   Gratzer, George (2016). „7-2 Podstawowe obiekty”. Teoria kraty. specjalne tematy i aplikacje . Cham, Szwajcaria: Birkäuser. ISBN 978-3319442358 .
•   Kleinberg, Jon; Tardos, Éva (2005). Projektowanie algorytmów . ISBN 0-321-29535-8 .
•   Knuth, Donald (1973). „5.1.1 Inwersje”. Sztuka programowania komputerowego . Pub Addison-Wesley. Co ISBN 0201896850 .
•   Mahmud, Hosam Mahmud (2000). „Sortowanie nielosowych danych”. Sortowanie: teoria dystrybucji . Szeregi Wileya-Interscience'a w matematyce dyskretnej i optymalizacji. Tom. 54. Wiley-IEEE. ISBN 978-0-471-32710-3 .
•   Pemmaraju, Sriram V.; Skiena, Steven S. (2003). „Permutacje i kombinacje”. Obliczeniowa matematyka dyskretna: kombinatoryka i teoria grafów z Mathematica . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-80686-2 .
•   Vitter, JS; Flajolet, Ph. (1990). „Analiza średnich przypadków algorytmów i struktur danych”. W van Leeuwen, Jan (red.). Algorytmy i złożoność . Tom. 1 (wyd. 2). Elsevier. ISBN 978-0-444-88071-0 .

Dalsza lektura

• Margoliusz, Barbara H. (2001). „Permutacje z inwersjami”. Dziennik sekwencji liczb całkowitych . 4 .

Miary presortowania

• Mannila, Heikki (kwiecień 1985). „Miary presortowania i optymalne algorytmy sortowania”. Transakcje IEEE na komputerach . C-34 (4): 318–325. doi : 10.1109/tc.1985.5009382 .
• Estivill-Castro, Władimir; Drewno, Derick (1989). „Nowa miara presortowania” . Informacja i obliczenia . 83 (1): 111–119. doi : 10.1016/0890-5401(89)90050-3 .
•   Skiena, Steven S. (1988). „Wkraczające listy jako miara presortowości”. BIT . 28 (4): 755–784. doi : 10.1007/bf01954897 . S2CID 33967672 .