Inverze (diskrétní matematika) - Inversion (discrete mathematics)

Permutace se zvýrazněnou jednou z jejích inverzí

Může to být označeno dvojicí míst (2, 4) nebo dvojicí prvků (5, 2).

v počítačová věda a diskrétní matematika, sekvence má inverze kde dva z jeho prvků jsou mimo svou přirozenost objednat.

Definice

Inverze

Nechat ${displaystyle pi}$ být permutace. Li ${displaystyle i$ a ${displaystyle pi (i)> pi (j)}$ , buď dvojice míst ${displaystyle (i, j)}$ ^[1]^[2] nebo dvojice prvků ${displaystyle {igl (} pi (i), pi (j) {igr)}}$ ^[3]^[4]^[5] se nazývá inverze z ${displaystyle pi}$ .

Inverze je obvykle definována pro permutace, ale může být definována také pro sekvence:
Nechat ${displaystyle S}$ být sekvence (nebo multiset permutace^[6]). Li ${displaystyle i$ a ${displaystyle S (i)> S (j)}$ , buď dvojice míst ${displaystyle (i, j)}$ ^[6]^[7] nebo dvojice prvků ${displaystyle {igl (} S (i), S (j) {igr)}}$ ^[8] se nazývá inverze ${displaystyle S}$ .

U sekvencí nejsou inverze podle definice založené na prvcích jedinečné, protože různé páry míst mohou mít stejnou dvojici hodnot.

The inverzní sada je množina všech inverzí. Sada inverzí permutace podle definice založené na místě je definice inverzní permutační inverzní sada podle definice založené na prvcích a naopak,^[9] jen s prvky vyměněných párů.

Inverzní číslo

The inverzní číslo je mohutnost inverzní množiny. Jedná se o běžnou míru tříditelnosti permutace^[5] nebo sekvence.^[8]

Je to počet přechodů ve šipkovém diagramu permutace,^[9] své Vzdálenost Kendall tau z permutace identity a součet každého z vektorů souvisejících s inverzí definovaných níže.

Nezáleží na tom, zda se k definování čísla inverze používá místní nebo elementární definice inverze, protože permutace a její inverze mají stejný počet inverzí.

Mezi další měřítka (před) seřazení patří minimální počet prvků, které lze ze sekvence odstranit, čímž se získá plně seřazená sekvence, počet a délky seřazených „běhů“ v sekvenci, stupačka Spearman (součet vzdáleností každého prvek z jeho seřazené pozice) a nejmenší počet výměn potřebných k seřazení sekvence.^[10] Standard srovnávací třídění algoritmy lze upravit tak, aby vypočítávaly číslo inverze v čase $Ó(n log n)$ .^[11]

Vektory související s inverzí

Používají se tři podobné vektory, které kondenzují inverze permutace do vektoru, který ji jednoznačně určuje. Často se jim říká inverzní vektor nebo Lehmerův kód. (Seznam zdrojů je nalezen tady.)

Tento článek používá tento výraz inverzní vektor ( ${displaystyle v}$ ) jako Wolfram.^[12] Zbývající dva vektory se někdy nazývají vlevo, odjet a pravý inverzní vektor, ale aby nedošlo k záměně s inverzním vektorem, tento článek je nazývá počet inverzí vlevo ( ${displaystyle l}$ ) a počet pravých inverzí ( ${displaystyle r}$ ). Interpretováno jako číslo faktoriálu počet inverze doleva dává permutacím reverzní kolexikografii,^[13] a počet správných inverzí dává lexikografický index.

Rotheho diagram

Inverzní vektor ${displaystyle v}$ :
S na základě prvků definice ${displaystyle v (i)}$ je počet inverzí, jejichž menší (pravá) složka je ${displaystyle i}$ .^[3]

{displaystyle v (i)}

je počet prvků v

{displaystyle pi}

větší než

{displaystyle i}

před

{displaystyle i}

.

{displaystyle v (i) ~~ = ~~ # {kmid k> i ~ land ~ pi ^ {- 1} (k)

Počet inverzí vlevo ${displaystyle l}$ :
S místně definice ${displaystyle l (i)}$ je počet inverzí, jejichž větší (pravá) složka je ${displaystyle i}$ .

{displaystyle l (i)}

je počet prvků v

{displaystyle pi}

větší než

{displaystyle pi (i)}

před

{displaystyle pi (i)}

.

{displaystyle l (i) ~~ = ~~ # left {kmid k

Počet pravých inverzí ${displaystyle r}$ , často volané Lehmerův kód:
S místně definice ${displaystyle r (i)}$ je počet inverzí, jejichž menší (vlevo) komponenta je ${displaystyle i}$ .

${displaystyle r (i)}$ je počet prvků v ${displaystyle pi}$ menší než ${displaystyle pi (i)}$ po ${displaystyle pi (i)}$ .

${displaystyle r (i) ~~ = ~~ # {kmid k> i ~ land ~ pi (k)$

Oba ${displaystyle v}$ a ${displaystyle r}$ lze najít pomocí a Rotheho diagram, což je permutační matice s 1s představovanými tečkami a inverzí (často znázorněnou křížkem) v každé poloze, která má tečku vpravo a pod ní. ${displaystyle r (i)}$ je součet inverzí v řadě ${displaystyle i}$ Rotheho diagramu, zatímco ${displaystyle v (i)}$ je součet inverzí ve sloupci ${displaystyle i}$ . Permutační matice inverze je tedy transpozice ${displaystyle v}$ permutace je ${displaystyle r}$ jeho inverzní a naopak.

Příklad: Všechny permutace čtyř prvků

Šest možných inverzí 4prvkové permutace

Následující tabulka se seznamem ukazuje 24 permutací čtyř prvků s jejich místními inverzními sadami, vektory souvisejícími s inverzí a čísly inverzí. (Malé sloupce jsou odrazy sloupců vedle nich a lze je použít k seřazení kolexikografický řád.)

Je to vidět ${displaystyle v}$ a ${displaystyle l}$ vždy mají stejné číslice, a to ${displaystyle l}$ a ${displaystyle r}$ oba souvisí se sadou inverze založené na místě. Netriviální prvky ${displaystyle l}$ jsou součty sestupných úhlopříček zobrazeného trojúhelníku a součty ${displaystyle r}$ jsou součty vzestupných úhlopříček. (Páry v sestupných úhlopříčkách mají pravé komponenty 2, 3, 4 společné, zatímco páry ve vzestupných úhlopříčkách mají levé komponenty 1, 2, 3 společné.)

Výchozí pořadí tabulky je obrácené colexové pořadí podle ${displaystyle pi}$ , což je stejné jako colexové pořadí od ${displaystyle l}$ . Lex objednat do ${displaystyle pi}$ je stejné jako lexové pořadí podle ${displaystyle r}$ .

Tříprvkové permutace pro srovnání


0
1
2
3
4
5

	${displaystyle pi}$		${displaystyle v}$			${displaystyle l}$	${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}$	${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

Slabé pořadí permutací

Permutohedron z symetrická skupina S₄

Sada permutací zapnuta n položky mohou mít strukturu a částečná objednávka, nazvaný slabé pořadí permutací, který tvoří a mříž.

Hasseův diagram inverzních sad seřazený podle podmnožina vztah tvoří kostra a permutohedron.

Pokud je každé inverzní sadě přiřazena permutace pomocí definice založené na místě, výsledné pořadí permutací je pořadí permutohedronu, kde hrana odpovídá zaměnění dvou prvků s následnými hodnotami. Toto je slabé pořadí permutací. Identita je jeho minimum a permutace tvořená obrácením identity je jeho maximum.

Pokud by ke každé inverzní sadě byla přiřazena permutace pomocí definice založené na prvcích, výsledné pořadí permutací by bylo pořadí Cayleyův graf, kde hrana odpovídá zaměnění dvou prvků na po sobě jdoucích místech. Tento Cayleyův graf symetrické skupiny je podobný jeho permutohedronu, ale s každou permutací nahrazenou inverzní.

Viz také

Sekvence v OEIS:

Sekvence související s reprezentací faktoriální základny
Faktorová čísla: A007623 a A108731
Inverzní čísla: A034968
Inverzní sady konečných permutací interpretované jako binární čísla: A211362 (související permutace: A211363 )
Konečné permutace, které mají ve svých inverzních vektorech pouze 0 a 1 s: A059590 (jejich inverzní sady: A211364 )
Počet obměn n prvky s k inverze; Mahonská čísla: A008302 (jejich řádková maxima; čísla Kendall-Manna: A000140 )
Počet připojených označených grafů s n hrany a n uzly: A057500

Reference

^ Aigner 2007, s. 27.
^ Kometa 1974, str. 237.
^ ^A ^b Knuth 1973, s. 11.
^ Pemmaraju & Skiena 2003, s. 69.
^ ^A ^b Vitter & Flajolet 1990, str. 459.
^ ^A ^b Bóna 2012, str. 57.
^ Cormen a kol. 2001, s. 39.
^ ^A ^b Barth & Mutzel 2004, s. 183.
^ ^A ^b Gratzer 2016, str. 221.
^ Mahmoud 2000, str. 284.
^ Kleinberg & Tardos 2005, str. 225.
^ Weisstein, Eric W. „Inverzní vektor“ Z MathWorld - Webový zdroj Wolfram
^ Opačné pořadí kolexu konečných permutací (sekvence A055089 v OEIS )

Zdrojová bibliografie

Aigner, Martin (2007). "Reprezentace slov". Kurz výčtu. Berlín, New York: Springer. ISBN 3642072534.
Barth, Wilhelm; Mutzel, Petra (2004). „Jednoduché a efektivní křížové počítání s dvojitou vrstvou“. Journal of Graph Algorithms and Applications. 8 (2): 179–194. doi:10,7155 / jgaa 00088.
Bóna, Miklósi (2012). "2.2 Převody v permutacích multisetů". Kombinatorika permutací. Boca Raton, FL: CRC Press. ISBN 1439850518.
Comtet, Louis (1974). "6.4 Převody permutace [n]". Pokročilá kombinatorika; umění konečných a nekonečných expanzí. Dordrecht, Boston: D. Reidel Pub. Co. ISBN 9027704414.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. ISBN 0-262-53196-8.
Gratzer, Georgi (2016). "7-2 Základní objekty". Teorie mřížky. speciální témata a aplikace. Cham, Švýcarsko: Birkhäuser. ISBN 331944235X.
Kleinberg, Jon; Tardos, Éva (2005). Návrh algoritmu. ISBN 0-321-29535-8.
Knuth, Donald (1973). „5.1.1 Inverze“. Umění počítačového programování. Addison-Wesley Pub. Co. ISBN 0201896850.
Mahmoud, Hosam Mahmoud (2000). Msgstr "Třídění náhodných dat". Třídění: teorie distribuce. Wiley-Interscience série v diskrétní matematice a optimalizaci. 54. Wiley-IEEE. ISBN 978-0-471-32710-3.
Pemmaraju, Sriram V .; Skiena, Steven S. (2003). "Permutace a kombinace". Výpočetní diskrétní matematika: kombinatorika a teorie grafů s Mathematica. Cambridge University Press. ISBN 978-0-521-80686-2.
Vitter, J.S .; Flajolet, Ph. (1990). "Průměrná případová analýza algoritmů a datových struktur". v van Leeuwen, Jan (vyd.). Algoritmy a složitost. 1 (2. vyd.). Elsevier. ISBN 978-0-444-88071-0.

Další čtení

Margolius, Barbara H. (2001). "Permutace s převrácením". Journal of Integer Sequences. 4.

Opatření předřazenosti

Mannila, Heikki (1984). Msgstr "Míry předběžného třídění a optimální třídicí algoritmy". Přednášky z informatiky. 172: 324–336. doi:10.1007/3-540-13345-3_29.
Estivill-Castro, Vladimir; Dřevo, Dericku (1989). „Nová míra předřazenosti“. Informace a výpočet. 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.
Skiena, Steven S. (1988). Msgstr "Zasahující seznamy jako měřítko předřazenosti". BIT. 28 (4): 755–784. doi:10.1007 / bf01954897.

[FOOTNOTEAigner200727-1] ^ Aigner 2007, s. 27.

[FOOTNOTEComtet1974237-2] ^ Kometa 1974, str. 237.

[FOOTNOTEKnuth197311-3] ^ ^A ^b Knuth 1973, s. 11.

[FOOTNOTEPemmarajuSkiena200369-4] ^ Pemmaraju & Skiena 2003, s. 69.

[FOOTNOTEVitterFlajolet1990459-5] ^ ^A ^b Vitter & Flajolet 1990, str. 459.

[FOOTNOTEBóna201257-6] ^ ^A ^b Bóna 2012, str. 57.

[FOOTNOTECormenLeisersonRivestStein200139-7] ^ Cormen a kol. 2001, s. 39.

[FOOTNOTEBarthMutzel2004183-8] ^ ^A ^b Barth & Mutzel 2004, s. 183.

[FOOTNOTEGratzer2016221-9] ^ ^A ^b Gratzer 2016, str. 221.

[FOOTNOTEMahmoud2000284-10] ^ Mahmoud 2000, str. 284.

[FOOTNOTEKleinbergTardos2005225-11] ^ Kleinberg & Tardos 2005, str. 225.

[12] ^ Weisstein, Eric W. „Inverzní vektor“ Z MathWorld - Webový zdroj Wolfram

[13] ^ Opačné pořadí kolexu konečných permutací (sekvence A055089 v OEIS )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]