Orde lexicogràfic

En matemàtiques, o més particularment en Teoria de l'orde, el orde lexicogràfic és una relació d'orde definida sobre el producte cartesiano de conjunts ordenats. És conegut principalment per la seua aplicació a cadenes de caràcters, per eixemple en diccionaris o en la guia telefònica.

Definició matemàtica

Definició en el cas d'un producte de dos conjunts

siguen $(A, \leq_{A})$ i $(B, \leq_{B})$ dos conjunts parcialment ordenats per les relacions $\leq_{A}$ i $\leq_{B}$ , respectivament, llavors un orde lexicogràfic és una relació d'orde parcial $\leq_{A, B}$ definida com seguix:

\forall (a, b), (a^{'}, b^{'}) \in A \times B :

(a, b) \leq_{A, B} (a^{'}, b^{'}) \Leftrightarrow a <_{A} a^{'} \lor (a = a^{'} \land b \leq_{B} b^{'})

Si $\leq_{A}$ i $\leq_{B}$ són órdens totals, $\leq_{A, B}$ també és un orde total.

Productes cartesianos n-aris

La definició dalt mencionada, que solament definix una relació d'orde en productes cartesianos de dos conjunts ordenats, es pot estendre a productes cartesianos n-aris, traent profit de la definició recursiva d'ells

\prod_{i = 1}^{1} A_{i} : = A_{1}

\prod_{i = 1}^{n + 1} A_{i} : = (\prod_{i = 1}^{n} A_{i}) \times A_{n + 1}, n \geq 1

que solament basa en l'aplicació múltiple del producte cartesiano binario.

Cadenes de caràcters

Una aplicació més general de l'orde lexicogràfic és en comparar cadenes de caràcters. Distint al cas per als productes cartesianos n-aris mencionats dalt, les cadenes de caràcters no posseïxen llongitut fixa. Usant la mateixa idea de definició recursiva que per al cas anterior, ara devem considerar el que una seqüència pot ser més llarga que l'atra, i que per lo tant termine de recórrer-se mentres que encara queden caràcters en l'atra.

La seqüència més curta a considerar serà la cadena buida $ϵ$ , és dir:

\forall b \in Σ^{*} : ϵ \leq b

Aixina, la definició recursiva queda:

\forall [a_{1} \dots a_{m}], [b_{1} \dots b_{n}] \in Σ^{*} ∖ {ϵ} : [a_{1} \dots a_{m}] \leq [b_{1} \dots b_{n}] \Leftrightarrow a_{1} < b_{1} \lor (a_{1} = b_{1} \land [a_{2} \dots a_{m}] \leq [b_{2} \dots b_{n}])

Eixemples i propietats

L'orde lexicogràfic no és igual a l'orde numèric

Si a = [19] i b = [138] tenim que b < a, perque el prefix és a₁ = b₁ = 1 i b₂ = 3 < a₂ = 9.

Els diccionaris són l'eixemple més conegut d'ordenament lexicogràfic. En este cas, no es fa distinció entre mayúscules i minúscules, i es considera per lo tant que a=A, b=B, c=C, etc.
El producte de dos grups ordenats en l'orde lexicogràfic és un grup ordenat.

Vore també

Problemes de l'orde lexicogràfic en Wikipedia

Este artícul conté una traducció derivada de «Orden lexicográfico» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.