Orden lexicográfico

En matemáticas , el orden lexicográfico ( también conocido como orden léxico u orden de diccionario ) es una generalización del orden alfabético de los diccionarios a secuencias de símbolos ordenados o, más generalmente, de elementos de un conjunto totalmente ordenado .

Existen diversas variantes y generalizaciones del ordenamiento lexicográfico. Una variante se aplica a secuencias de distinta longitud comparando la longitud de las secuencias antes de considerar sus elementos.

Otra variante, ampliamente utilizada en combinatoria , ordena subconjuntos de un conjunto finito dado asignando un orden total a dicho conjunto y convirtiendo los subconjuntos en secuencias crecientes , a las que se aplica el orden lexicográfico.

Una generalización define un orden en un producto cartesiano n -ario de conjuntos parcialmente ordenados ; este orden es un orden total si y solo si todos los factores del producto cartesiano están totalmente ordenados.

Las palabras de un léxico (el conjunto de palabras utilizadas en un idioma) tienen un orden convencional, empleado en diccionarios y enciclopedias , que depende del orden subyacente del alfabeto de símbolos que las compone. El orden lexicográfico es una forma de formalizar el orden de las palabras a partir del orden de los símbolos subyacentes.

La noción formal parte de un conjunto finito A , a menudo llamado alfabeto , que es totalmente ordenado . Es decir, para cualesquiera dos símbolos a y b en A que no sean el mismo símbolo, se cumple exactamente una de las siguientes condiciones: a < b o b < a .

Las palabras de A son secuencias finitas de símbolos de A , incluyendo palabras de longitud 1 que contienen un solo símbolo, palabras de longitud 2 con 2 símbolos, y así sucesivamente, incluso incluyendo la secuencia vacía.${\displaystyle \varepsilon }$sin ningún símbolo. El orden lexicográfico en el conjunto de todas estas palabras finitas ordena las palabras de la siguiente manera:

1. Dadas dos palabras diferentes de la misma longitud, digamos a = a ₁ a ₂ ... a _k y b = b ₁ b ₂ ... b _k , el orden de las dos palabras depende del orden alfabético de los símbolos en el primer lugar i donde difieren las dos palabras (contando desde el principio de las palabras): a < b si y solo si a _i < b _i en el orden subyacente del alfabeto A .
2. Si dos palabras tienen longitudes diferentes, el orden lexicográfico habitual rellena la más corta con "espacios en blanco" (un símbolo especial que se trata como menor que cualquier elemento de A ) al final hasta que las palabras tengan la misma longitud, y luego las palabras se comparan como en el caso anterior.

Sin embargo, en combinatoria , se suele utilizar otra convención para el segundo caso, según la cual una secuencia más corta siempre es menor que una secuencia más larga. Esta variante del orden lexicográfico se denomina a veces orden shortlex .

En orden lexicográfico, la palabra "Thomas" aparece antes que "Thompson" porque se diferencian en la quinta letra ('a' y 'p'), y la letra 'a' precede a la 'p' en el alfabeto. Dado que es la primera diferencia, en este caso la quinta letra es la "diferencia más significativa" para el orden alfabético.

Una propiedad importante del orden lexicográfico es que para cada n , el conjunto de palabras de longitud n está bien ordenado por el orden lexicográfico (siempre que el alfabeto sea finito); es decir, toda secuencia decreciente de palabras de longitud n es finita (o equivalentemente, todo subconjunto no vacío tiene un elemento mínimo). ^{[ 1 ] [ 2 ]} No es cierto que el conjunto de todas las palabras finitas esté bien ordenado; por ejemplo, el conjunto infinito de palabras {b, ab, aab, aaab, ... } no tiene ningún elemento lexicográficamente más antiguo.

El orden lexicográfico se utiliza no solo en los diccionarios, sino también comúnmente para números y fechas.

Una de las desventajas del sistema de numeración romano es que no siempre resulta obvio cuál de dos números es menor. Por otro lado, con la notación posicional del sistema de numeración indoarábigo , comparar números es sencillo, ya que el orden natural de los números naturales coincide con la variante shortlex del orden lexicográfico. De hecho, con la notación posicional, un número natural se representa mediante una secuencia de dígitos numéricos , y un número natural es mayor que otro si tiene más dígitos (sin contar los ceros iniciales) o si el número de dígitos es el mismo y el primer dígito (el más significativo) que difiere es mayor.

Para los números reales escritos en notación decimal , se utiliza una variante ligeramente diferente del orden lexicográfico: las partes a la izquierda del punto decimal se comparan como antes; si son iguales, las partes a la derecha del punto decimal se comparan siguiendo el orden lexicográfico. El espacio en blanco en este contexto es un dígito "0" al final.

Cuando se consideran números negativos, es necesario invertir el orden de comparación. Esto no suele ser un problema para los humanos, pero sí para las computadoras (la comprobación del signo requiere tiempo). Esta es una de las razones por las que se adoptó la representación en complemento a dos para representar números enteros con signo en las computadoras.

Otro ejemplo de uso no convencional del orden lexicográfico se encuentra en la norma ISO 8601 para fechas, que las expresa como AAAA-MM-DD. Este esquema de formato tiene la ventaja de que el orden lexicográfico de las secuencias de caracteres que representan fechas coincide con el orden cronológico : una fecha anterior aparece más pequeña en el orden lexicográfico que una posterior. Esto se cumple para fechas desde el año 1 d. C. hasta el año 9999 d. C. Este ordenamiento de fechas facilita la clasificación computarizada de fechas al evitar la necesidad de un algoritmo de clasificación independiente.

El monoide de palabras sobre un alfabeto A es el monoide libre sobre A. Es decir, los elementos del monoide son las secuencias finitas (palabras) de elementos de A (incluida la secuencia vacía, de longitud 0), y la operación (multiplicación) es la concatenación de palabras. Una palabra u es un prefijo (o 'truncamiento') de otra palabra v si existe una palabra w tal que v = uw . Por esta definición, la palabra vacía (${\displaystyle \varepsilon }$) es un prefijo de cada palabra, y cada palabra es un prefijo de sí misma (con w${\displaystyle =\varepsilon }$); debe tenerse cuidado si se quieren excluir estos casos.

Con esta terminología, la definición anterior del orden lexicográfico se vuelve más concisa: Dado un conjunto A parcial o totalmente ordenado , y dos palabras a y b sobre A tales que b no es vacío, entonces se tiene a < b bajo el orden lexicográfico, si se cumple al menos una de las siguientes condiciones:

• a es un prefijo de b
• existen palabras u , v , w (posiblemente vacías) y elementos x e y de A tales que

x < y

a = uxv

b = uyw

Nótese que, debido a la condición de prefijo en esta definición,${\displaystyle \varepsilon <b\,\,{\text{ para todo }}b\neq \varepsilon ,}$dónde${\displaystyle \varepsilon }$es la palabra vacía.

Si${\displaystyle \,<\,}$es un pedido total en${\displaystyle A,}$Entonces, así es el orden lexicográfico en las palabras de${\displaystyle A.}$Sin embargo, en general esto no es un orden adecuado , incluso si el alfabeto${\displaystyle A}$está bien ordenado. Por ejemplo, si A = { a , b } , el lenguaje { a ⁿ b | n ≥ 0, b > ε } no tiene ningún elemento menor en el orden lexicográfico: ... < aab < ab < b .

Dado que muchas aplicaciones requieren buenos órdenes, a menudo se utiliza una variante de los órdenes lexicográficos. Este buen orden, a veces llamado shortlex u orden cuasi-lexicográfico , consiste en considerar primero las longitudes de las palabras (si length( a ) < length( b ) , entonces${\displaystyle a<b}$), y, si las longitudes son iguales, utilizando el orden lexicográfico. Si el orden en A es un buen orden, lo mismo ocurre con el orden shortlex. ^{[ 2 ] [ 3 ]}

El orden lexicográfico define un orden en un producto cartesiano n -ario de conjuntos ordenados, que es un orden total cuando todos estos conjuntos están a su vez totalmente ordenados. Un elemento de un producto cartesiano${\displaystyle E_{1}\times \cdots \times E_{n}}$es una secuencia cuya${\displaystyle i}$^El elemento pertenece a${\displaystyle E_{i}}$por cada${\displaystyle i.}$Dado que la evaluación del orden lexicográfico de las secuencias compara únicamente los elementos que tienen el mismo rango en las secuencias, el orden lexicográfico se extiende a los productos cartesianos de conjuntos ordenados.

Específicamente, dados dos conjuntos parcialmente ordenados${\displaystyle A}$y${\displaystyle B,}$elorden lexicográfico en el producto cartesiano${\displaystyle A\times B}$se define como $${\displaystyle (a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ si y solo si }}a<a^{\prime }{\text{ o }}\left(a=a^{\prime }{\text{ y }}b\leq b^{\prime }\right),}$$

El resultado es un pedido parcial. Si${\displaystyle A}$y${\displaystyle B}$Si cada uno está totalmente ordenado , entonces el resultado también es un orden total. El orden lexicográfico de dos conjuntos totalmente ordenados es, por lo tanto, una extensión lineal de su orden producto .

De forma similar, se puede definir el orden lexicográfico en el producto cartesiano de una familia infinita de conjuntos ordenados, si la familia está indexada por los números naturales , o más generalmente por un conjunto bien ordenado. Este orden lexicográfico generalizado es un orden total si cada conjunto de factores está totalmente ordenado.

A diferencia del caso finito, un producto infinito de bien ordenados no está necesariamente bien ordenado por el orden lexicográfico. Por ejemplo, el conjunto de secuencias binarias infinitas numerables (por definición, el conjunto de funciones de los números naturales a${\displaystyle \{0,1\},}$también conocido como el espacio Cantor${\displaystyle \{0,1\}^{\omega }}$) no está bien ordenado; el subconjunto de secuencias que tienen precisamente una${\displaystyle 1}$(es decir, { 100000..., 010000..., 001000..., ... } ) no tiene un elemento mínimo bajo el orden lexicográfico inducido por${\displaystyle 0<1,}$porque 100000... > 010000... > 001000... > ... es una cadena descendente infinita . ^{[ 1 ]} De manera similar, el producto lexicográfico infinito tampoco es noetheriano porque 011111... < 101111... < 110111 ... < ... es una cadena ascendente infinita.

Las funciones de un conjunto bien ordenado${\displaystyle X}$a un conjunto totalmente ordenado${\displaystyle Y}$pueden identificarse con secuencias indexadas por${\displaystyle X}$de elementos de${\displaystyle Y.}$Por lo tanto, pueden ordenarse según el orden lexicográfico, y para dos de esas funciones${\displaystyle f}$y${\displaystyle g,}$El orden lexicográfico está determinado, por lo tanto, por sus valores para el más pequeño.${\displaystyle x}$de tal manera que${\displaystyle f(x)\neq g(x).}$

Si${\displaystyle Y}$También está bien ordenado y${\displaystyle X}$es finito, entonces el orden resultante es un buen orden. Como se muestra arriba, si${\displaystyle X}$es infinito, este no es el caso.

En combinatoria , a menudo hay que enumerar y, por lo tanto, ordenar los subconjuntos finitos de un conjunto dado.${\displaystyle S.}$Para ello, normalmente se elige un orden en${\displaystyle S.}$Luego, ordenando un subconjunto de${\displaystyle S}$es equivalente a convertirlo en una secuencia creciente. El orden lexicográfico en las secuencias resultantes induce así un orden en los subconjuntos, que también se denomina orden lexicográfico .

En este contexto, generalmente se prefiere ordenar primero los subconjuntos por cardinalidad , como en el orden shortlex . Por lo tanto, a continuación, consideraremos únicamente órdenes en subconjuntos de cardinalidad fija.

Por ejemplo, utilizando el orden natural de los enteros, el orden lexicográfico en los subconjuntos de tres elementos de${\displaystyle S=\{1,2,3,4,5,6\}}$es

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <

234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456 .

Para ordenar subconjuntos finitos de una cardinalidad dada de los números naturales , el orden colexicográfico (véase más abajo) suele ser más conveniente, porque todos los segmentos iniciales son finitos y, por lo tanto, el orden colexicográfico define un isomorfismo de orden entre los números naturales y el conjunto de conjuntos de${\displaystyle n}$números naturales. Este no es el caso del orden lexicográfico, ya que, con el orden lexicográfico, tenemos, por ejemplo,${\displaystyle 12n<134}$por cada${\displaystyle n>2.}$

Dejar${\displaystyle \mathbb {Z} ^{n}}$ser el grupo abeliano libre de rango${\displaystyle n,}$cuyos elementos son secuencias de${\displaystyle n}$números enteros, y la operación es la suma . Un orden de grupo en${\displaystyle \mathbb {Z} ^{n}}$es un orden total , que es compatible con la suma, es decir $${\displaystyle a<b\quad {\text{ si y solo si }}\quad a+c<b+c.}$$

El ordenamiento lexicográfico es un orden de grupo en${\displaystyle \mathbb {Z} ^{n}.}$

El ordenamiento lexicográfico también puede utilizarse para caracterizar todos los órdenes de grupo en${\displaystyle \mathbb {Z} ^{n}.}$^{[ 4 ] [ 5 ]} De hecho,${\displaystyle n}$formas lineales con coeficientes reales , definen una aplicación desde${\displaystyle \mathbb {Z} ^{n}}$en${\displaystyle \mathbb {R} ^{n},}$que es inyectiva si las formas son linealmente independientes (también puede ser inyectiva si las formas son dependientes, véase más abajo). El orden lexicográfico en la imagen de este mapa induce un orden de grupo en${\displaystyle \mathbb {Z} ^{n}.}$El teorema de Robbiano establece que cualquier orden de grupo puede obtenerse de esta manera.

Más precisamente, dado un pedido grupal en${\displaystyle \mathbb {Z} ^{n},}$existe un número entero${\displaystyle s\leq n}$y${\displaystyle s}$formas lineales con coeficientes reales, de tal manera que el mapa inducido${\displaystyle \varphi }$de${\displaystyle \mathbb {Z} ^{n}}$en${\displaystyle \mathbb {R} ^{s}}$tiene las siguientes propiedades;

• ${\displaystyle \varphi }$es inyectivo;
• el isomorfismo resultante de${\displaystyle \mathbb {Z} ^{n}}$a la imagen de${\displaystyle \varphi }$es un isomorfismo de orden cuando la imagen está equipada con el orden lexicográfico en${\displaystyle \mathbb {R} ^{s}.}$

El orden colexicográfico o colex es una variante del orden lexicográfico que se obtiene leyendo secuencias finitas de derecha a izquierda en lugar de leerlas de izquierda a derecha. Más precisamente, mientras que el orden lexicográfico entre dos secuencias se define por

a ₁ a ₂ ... a _k < ^lex b ₁ b ₂ ... b _k si a _i < b _i para el primer i donde a _i y b _i difieren,

El orden colexicográfico se define por

a ₁ a ₂ ... a _k < ^colex b ₁ b ₂ ... b _k si a _i < b _i para el último i donde a _i y b _i difieren

En general, la diferencia entre el orden colexicográfico y el lexicográfico no es muy significativa. Sin embargo, al considerar secuencias crecientes, típicamente para subconjuntos de codificación, los dos órdenes difieren significativamente.

Por ejemplo, para ordenar las secuencias crecientes (o los conjuntos) de dos enteros naturales, el orden lexicográfico comienza por

12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ... ,

y el orden colexicográfico comienza por

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ... .

La principal propiedad del orden colexicográfico para secuencias crecientes de una longitud dada es que cada segmento inicial es finito. En otras palabras, el orden colexicográfico para secuencias crecientes de una longitud dada induce un isomorfismo de orden con los números naturales y permite enumerar estas secuencias. Esto se utiliza frecuentemente en combinatoria , por ejemplo, en la demostración del teorema de Kruskal-Katona . En cambio, las elipsis en el orden lexicográfico anterior omiten una infinidad de secuencias, lo que significa que, por ejemplo, el segmento inicial que termina en 23 es infinito.

Al considerar polinomios , el orden de los términos no importa en general, ya que la suma es conmutativa. Sin embargo, algunos algoritmos , como la división larga de polinomios , requieren que los términos estén en un orden específico. Muchos de los principales algoritmos para polinomios multivariados están relacionados con las bases de Gröbner , concepto que requiere la elección de un orden monomial , es decir, un orden total , que sea compatible con la estructura monoide de los monomios . Aquí "compatible" significa que${\displaystyle a<b{\text{ implies }}ac<bc,}$si la operación monoide se denota multiplicativamente. Esta compatibilidad implica que el producto de un polinomio por un monomio no cambia el orden de los términos. Para las bases de Gröbner, debe cumplirse una condición adicional, a saber, que todo monomio no constante sea mayor que el monomio 1. Sin embargo, esta condición no es necesaria para otros algoritmos relacionados, como los algoritmos para el cálculo del cono tangente .

Como las bases de Gröbner se definen para polinomios en un número fijo de variables, es común identificar monomios (por ejemplo${\displaystyle x_{1}x_{2}^{3}x_{4}x_{5}^{2}}$) con sus vectores exponenciales (aquí [1, 3, 0, 1, 2] ). Si n es el número de variables, cada orden monomial es, por lo tanto, la restricción a${\displaystyle \mathbb {N} ^{n}}$de un orden monomial de${\displaystyle \mathbb {Z} ^{n}}$(véase arriba §  Órdenes de grupo de Zn${\displaystyle \mathbb {Z} ^{n},}$para una clasificación).

Uno de estos órdenes admisibles es el orden lexicográfico. Históricamente, fue el primero en utilizarse para definir las bases de Gröbner, y a veces se le denomina orden lexicográfico puro para distinguirlo de otros órdenes que también están relacionados con un orden lexicográfico.

Otro método consiste en comparar primero los grados totales y luego resolver los conflictos mediante el orden lexicográfico. Este orden no se usa con frecuencia, ya que tanto el orden lexicográfico como el orden lexicográfico inverso de grados suelen tener mejores propiedades.

El orden lexicográfico inverso de grados consiste también en comparar primero los grados totales y, en caso de igualdad de los grados totales, utilizar el inverso del orden colexicográfico. Es decir, dados dos vectores de exponentes, uno tiene $${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$$ si alguno $${\displaystyle a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},}$$ o $${\displaystyle a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{ and }}\quad a_{i}>b_{i}{\text{ for the largest }}i{\text{ for which }}a_{i}\neq b_{i}.}$$

Para este ordenamiento, los monomios de grado uno tienen el mismo orden que las indeterminadas correspondientes (esto no ocurriría si se utilizara el orden lexicográfico inverso). Para comparar monomios en dos variables del mismo grado total, este orden es el mismo que el orden lexicográfico. Esto no sucede con más variables. Por ejemplo, para vectores exponenciales de monomios de grado dos en tres variables, se tiene para el grado el orden lexicográfico inverso: $${\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}$$

Para el orden lexicográfico, los mismos vectores de exponentes se ordenan como $${\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].}$$

Una propiedad útil del orden lexicográfico inverso de grado es que un polinomio homogéneo es múltiplo del menor indeterminado si y solo si su monomio principal (su monomio mayor) es múltiplo de este menor indeterminado.

• Colación
• Orden Kleene-Brouwer
• Preferencias lexicográficas : una aplicación del orden lexicográfico en economía.
• Optimización lexicográfica : un problema algorítmico que consiste en encontrar un elemento lexicográficamente máximo.
• Topología del orden lexicográfico en el cuadrado unitario
• Ordenación lexicográfica en la notación de índice abstracto tensorial
• Rotación de cadena lexicográficamente mínima
• Orden de Leximin
• Línea larga (topología)
• Lyndon palabra
• Preorden : el nombre del orden lexicográfico (de bits) en un recorrido de árbol binario .
• Producto estrella : una forma diferente de combinar pedidos parciales
• Orden de Shortlex
• Órdenes en el producto cartesiano de conjuntos totalmente ordenados

• Materiales de aprendizaje relacionados con el orden lexicográfico y colexicográfico en Wikiversidad.