Inversión (matemáticas)

En informática e matemáticas discretas, unha inversión nunha secuencia é un par de elementos que están fóra da súa orde natural.

Definicións

Inversión

Sexa $\pi$ unha permutación. Hai unha inversión de $\pi$ entre $i$ e $j$ se $i<j$ e $\pi (i)>\pi (j)$ . A inversión indícase mediante un par ordenado que contén calquera dos lugares $(i,j)$ ^[1] ^[2] ou os elementos ${\bigl (}\pi (i),\pi (j){\bigr )}$ .^[3] ^[4] ^[5]

O conxunto de inversión é o conxunto de todas as inversións. O conxunto de inversión dunha permutación que usa a notación baseada no lugar é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada en elementos cos dous compoñentes de cada par ordenado intercambiados. Do mesmo xeito, o conxunto de inversión dunha permutación que usa a notación baseada en elementos é o mesmo que o conxunto de inversión da permutación inversa usando a notación baseada no lugar cos dous compoñentes de cada par ordenado intercambiados.^[6]

As inversións adoitan definirse para as permutacións, mais tamén se poden definir para as secuencias:Sexa $S$ unha secuencia, se $i<j$ e $S(i)>S(j)$ , ben o par de lugares $(i,j)$ ^[7] ^[8] ou o par de elementos ${\bigl (}S(i),S(j){\bigr )}$ ^[9] chámase inversión de $S$ .

Para as secuencias, as inversións segundo a definición baseada en elementos non son únicas, porque diferentes pares de lugares poden ter o mesmo par de valores.

Número da inversión

O número da inversión ${\mathtt {inv}}(X)$ ^[10] dunha secuencia $X=\langle x_{1},\dots ,x_{n}\rangle$ , é a cardinalidade do conxunto de inversión. É unha medida común de ordenación (ás veces chamada preclasificación) dunha permutación^[5] ou secuencia. ^[9] O número de inversión está entre 0 e ${\frac {n(n-1)}{2}}$ inclusive. Unha permutación e a súa inversa teñen o mesmo número de inversión.

Por exemplo ${\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0$ xa que a secuencia está ordenada. Ademais, cando $n=2m$ é par, ${\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}$ (porque cada parella $(1\leq i\leq m<j\leq 2m)$ é unha inversión). Este último exemplo mostra que un conxunto intuitivamente "case ordenado" aínda pode ter un número cadrático de inversións.

O número de inversión é o número de cruzamentos no esquema de frecha da permutation,[6] a distancia tau de Kendall da permutación desde a identidade, e a suma de cada un dos vectores de inversión relacionados definidos abaixo.

Outras medidas de ordenación inclúen o número mínimo de elementos que se poden eliminar da secuencia para obter unha secuencia totalmente ordenada, a regra de pé de Spearman (suma das distancias de cada elemento dende a súa posición ordenada), e o menor número de trocos necesarios para ordenar a secuencia. ^[11] Os algoritmos estándar de ordenación por comparación pódense adaptar para calcular o número de inversión nun tempo $O(n log n)$ . ^[12]

Vectores relacionados coa inversión

Están en uso tres vectores similares que condensan as inversións dunha permutación nun vector que a determina de forma única. Adoitan chamarse vector de inversión ou código de Lehmer. (Atópase aquí unha lista de fontes).

Este artigo usa o termo vector de inversión ( $v$ ) como as páxinas de Wolfram Mathematica.^[13] Os dous vectores restantes ás veces chámanse vector de inversión pola esquerda e pola dereita, mais para evitar confusións co vector de inversión, este artigo chámaos conta de inversión pola esquerda ( $l$ ) e conta de inversión pola dereita ( $r$ ). Interpretado como un sistema de numeración factorial, a conta de inversión pola esquerda dá as permutacións colexicográficas inversas, ^[14] e a conta de inversión pola dereita dá o índice lexicográfico.

Vector de inversión $v$ :Coa definición baseada en elementos $v(i)$ é o número de inversións cuxo compoñente menor (dereito) é $i$ . ^[3]

v(i)

é o número de elementos en

\pi

máis grande cá

i

en posición anterior a

i

.

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

Conta de inversión pola esquerda $l$ :Coa definición baseada no lugar $l(i)$ é o número de inversións cuxo compoñente (dereito) maior é $i$ .

l(i)

é o número de elementos en

\pi

máis grande cá

\pi (i)

en posición anterior a

\pi (i)

.

l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}

Conta de inversións pola dereita $r$ , a miúdo chamado código de Lehmer :Coa definición baseada no lugar $r(i)$ é o número de inversións cuxa compoñente menor (esquerda) é $i$ .

r(i)

é o número de elementos en

\pi

menor que

\pi (i)

posteriores a

\pi (i)

.

r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}

Ambos os $v$ e $r$ pódense atopar coa axuda dun diagrama de Rothe, que é unha matriz de permutación cos 1 representados por puntos, e unha inversión (a miúdo representada por unha cruz) en cada posición que teña un punto á dereita e debaixo dela. $r(i)$ é a suma das inversións na fila $i$ do diagrama de Rothe, mentres que $v(i)$ é a suma das inversións na columna $i$ . A matriz de permutación da inversa é a transposta, polo tanto o $v$ dunha permutación é o $r$ da súa inversa, e viceversa.

Exemplo: todas as permutacións de catro elementos

A seguinte táboa ordenada mostra as 24 permutacións de catro elementos (na columna $\pi$ ) cos seus conxuntos de inversión baseados no lugar (na columna p-b), os vectores relacionados coa inversión (nas columnas $v$ , $l$ , e $r$ ) e os números de inversión (na columna #). (As columnas con letra máis pequena e sen título son reflexos das columnas situadas ao lado, e pódense usar para ordenar por orde colexicográfica).

Pódese ver que $v$ e $l$ sempre teñen os mesmos díxitos, e que tano $l$ como $r$ están relacionados co conxunto de inversión baseado no lugar. Os elementos non triviais de $l$ son as sumas das diagonais descendentes do triángulo mostrado e os de $r$ son as sumas das diagonais ascendentes. (Os pares en diagonais descendentes teñen en común as compoñentes dereitas 2, 3, 4, mentres que os pares en diagonais ascendentes teñen en común as compoñentes esquerdas 1, 2, 3).

A orde predeterminada da táboa é a orde "colex" inversa por $\pi$ , que é o mesmo que a orde colex por $l$ . A orde "lex" por $\pi$ é o mesmo que a orde "lex" por $r$ .

Permutacións de 3 elementos para comparación

0


0
1
2
3
4
5

	$\pi$		$v$			$l$	$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

11


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

	$\pi$		$v$			$l$	$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

Orde feble de permutacións

Ao conxunto de permutacións de n elementos pódeselle dar a estrutura dunha orde parcial, chamada orde feble de permutacións, que forma unha retícula.

O diagrama de Hasse dos conxuntos de inversión ordenados pola relación de subconxuntos forma o esqueleto dun permutoedro.

Se se asignase unha permutación a cada conxunto de inversión usando a definición baseada en elementos, a orde resultante das permutacións sería a dun grafo de Cayley, onde unha aresta corresponde ao troco de dous elementos en lugares consecutivos. Este grafo de Cayley do grupo simétrico é semellante ao seu permutoedro, mais con cada permutación substituída pola súa inversa.

Notas

↑ Aigner 2007.
↑ Comtet 1974.
1 2 Knuth 1973.
↑ Pemmaraju & Skiena 2003.
1 2 Vitter & Flajolet 1990.
↑ Gratzer 2016.
↑ Bóna 2012.
↑ Cormen et al. 2001.
1 2 Barth & Mutzel 2004.
↑ Mannila 1985.
↑ Mahmoud 2000.
↑ Kleinberg & Tardos 2005.
↑ Weisstein, Eric W. "Inversion Vector" From MathWorld--A Wolfram Web Resource
↑ Reverse colex order of finitary permutations (secuencia [[OEIS:{{{id}}}|{{{id}}}]] na OEIS)

Véxase tamén

Bibliografía

Aigner, Martin (2007). "Word Representation". A course in enumeration. Berlin, New York: Springer. ISBN 978-3642072536.
Barth, Wilhelm; Mutzel, Petra (2004). "Simple and Efficient Bilayer Cross Counting". Journal of Graph Algorithms and Applications 8 (2): 179–194. doi:10.7155/jgaa.00088.
Bóna, Miklós (2012). "2.2 Inversions in Permutations of Multisets". Combinatorics of permutations. Boca Raton, FL: CRC Press. ISBN 978-1439850510.
Comtet, Louis (1974). "6.4 Inversions of a permutation of [n]". Advanced combinatorics; the art of finite and infinite expansions. Dordrecht, Boston: D. Reidel Pub. Co. ISBN 9027704414.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
Gratzer, George (2016). "7-2 Basic objects". Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. ISBN 978-3319442358.
Kleinberg, Jon; Tardos, Éva (2005). Algorithm Design. ISBN 0-321-29535-8.
Knuth, Donald (1973). "5.1.1 Inversions". The Art of Computer Programming. Addison-Wesley Pub. Co. ISBN 0201896850.
Mahmoud, Hosam Mahmoud (2000). "Sorting Nonrandom Data". Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization 54. Wiley-IEEE. ISBN 978-0-471-32710-3.
Pemmaraju, Sriram V.; Skiena, Steven S. (2003). "Permutations and combinations". Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. ISBN 978-0-521-80686-2.
Vitter, J.S.; Flajolet, Ph. (1990). "Average-Case Analysis of Algorithms and Data Structures". En van Leeuwen, Jan. Algorithms and Complexity 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0.

Outros artigos

[FOOTNOTEAigner2007-1] Aigner 2007.

[FOOTNOTEComtet1974-2] Comtet 1974.

[FOOTNOTEKnuth1973-3] 1 2 Knuth 1973.

[FOOTNOTEPemmarajuSkiena2003-4] Pemmaraju & Skiena 2003.

[FOOTNOTEVitterFlajolet1990-5] 1 2 Vitter & Flajolet 1990.

[FOOTNOTEGratzer2016-6] Gratzer 2016.

[FOOTNOTEBóna2012-7] Bóna 2012.

[FOOTNOTECormenLeisersonRivestStein2001-8] Cormen et al. 2001.

[FOOTNOTEBarthMutzel2004-9] 1 2 Barth & Mutzel 2004.

[FOOTNOTEMannila1985-10] Mannila 1985.

[FOOTNOTEMahmoud2000-11] Mahmoud 2000.

[FOOTNOTEKleinbergTardos2005-12] Kleinberg & Tardos 2005.

[13] Weisstein, Eric W. "Inversion Vector" From MathWorld--A Wolfram Web Resource

[14] Reverse colex order of finitary permutations (secuencia [[OEIS:{{{id}}}|{{{id}}}]] na OEIS)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]