Orden lexicográfico

El orden lexicográfico es una relación de orden que se utiliza para ordenar producto cartesiano de conjuntos ordenos. Está conocido mayormente por su aplicación a cadenas de caracteres, por ejemplo en diccionarios o en la guía telefónica.

Definición matemática

Pares

Matemáticamente, sean $(A,\leq _{A})$ y $(B,\leq _{B})$ dos conjuntos parcialmente ordenados por las relaciones $\leq _{A}$ y $\leq _{B}$, respectivamente, entonces un orden lexicográfico es una relación de orden parcial $\leq _{A,B}$ definida como sigue:

$\forall (a,b),(a',b')\in A\times B:$

$(a,b)\leq _{A,B}(a',b')\ \Leftrightarrow \ a<a'\vee (a=a'\wedge b\leq b')$

Si $\leq _{A}$ y $\leq _{B}$ son ordenes totales, $\leq _{A,B}$ también es un orden total.

Productos cartesianos n-arios

La definición arriba mencionada, que sólo define una relación de orden en productos cartesianos de dos conjuntos ordenados, se puede extender a productos cartesianos n-arios sacando provecho de la definición recursiva de ellos

$\prod _{i=1}^{1}A_{i}:=A_{1}$

$\prod _{i=1}^{n+1}A_{i}:=\left(\prod _{i=1}^{n}A_{i}\right)\times A_{n+1},n\geq 1$

que sólo basa en la aplicación múltiple del producto cartesiano binario.

Secuencias de caracteres

Una aplicación mayor del orden lexicográfico es el orden de secuencias de caracteres. Pero distinto a los productos cartesianos n-arios mencionados arriba, secuencias de caracteres no tienen longitud fija. Usando el mismo concepto de la definición recursiva, como en la definición del orden lexicográfico en productos cartesianos n-arios, ahora nos enfrentamos a la situación que una secuencia es más larga que la otra, asi qué durante la recursión ya puede haber terminado una secuencia mientras quedan letras en la otra. Para resolver este caso definimos que la secuencia más corta sea el elemento menor (primera línea en la definición recursiva a continuación):

$\forall b\in \Sigma ^{*}:\epsilon \leq b$

$\forall [a_{1}\dots a_{n_{a}}],[b_{1}\dots b_{n_{b}}]\in \Sigma ^{*}\backslash \{\epsilon \}:[a_{1}\dots a_{n_{a}}]\leq [b_{1}\dots b_{n_{b}}]\Leftrightarrow a_{1}<b_{1}\vee (a_{1}=b_{1}\wedge [a_{2}\dots a_{n_{a}}]\leq [b_{2}\dots a_{n_{b}}])$

Ejemplos

• El orden lexicográfico no es igual al orden numérico
  

Si a = [19] y b = [138] tenemos que b < a, porque el prefijo es a₁ = b₁ = 1 y b₂ = 3 < a₂ = 9.

• Diccionarios
  

Los diccionarios son el ejemplo más conocido de ordenamiento lexicográfico. En este caso, eso sí, no se hace distinción entre mayúsculas y minúsculas.

Véase también

• Problemas del orden lexicográfico en Wikipedia