Orden lexicográfico

Generalization of the alphabetical order of dictionaries to sequences of elements of an ordered set

En matemáticas , el orden lexicográfico o lexicográfico (también conocido como orden léxico , u orden del 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 orden lexicográfico. Una variante se aplica a secuencias de diferentes longitudes, comparando las longitudes 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 al conjunto finito, 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 sólo si todos los factores del producto cartesiano están totalmente ordenados.

Definición

Las palabras de un léxico (el conjunto de palabras que se utilizan en una lengua) tienen un ordenamiento convencional, utilizado en diccionarios y enciclopedias , que depende del ordenamiento subyacente del alfabeto de símbolos que se utiliza para construir las palabras. El orden lexicográfico es una forma de formalizar el orden de las palabras dado el orden de los símbolos subyacentes.

La noción formal comienza con un conjunto finito A , a menudo llamado alfabeto , que está totalmente ordenado . Es decir, para cualesquiera dos símbolos a y b en A que no sean el mismo símbolo, a < b o b < a .

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

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 primer lugar i donde las dos palabras difieren (contando desde el comienzo 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 más pequeño que cada elemento de A ) al final hasta que las palabras tienen la misma longitud, y luego se comparan las palabras como en el caso anterior.

Sin embargo, en combinatoria , se utiliza con frecuencia otra convención para el segundo caso, según la cual una secuencia más corta siempre es más pequeña 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 de "Thompson" porque se diferencian por primera vez en la quinta letra ('a' y 'p'), y la letra 'a' aparece antes de la letra 'p' en el alfabeto. Como 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, cada secuencia decreciente de palabras de longitud n es finita (o equivalentemente, cada 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.

Sistemas de numeración y fechas

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

Una de las desventajas del sistema de numeración romana es que no siempre es inmediatamente obvio cuál de los dos números es el menor. Por otro lado, con la notación posicional del sistema de numeración hindú-arábigo , comparar números es fácil, porque el orden natural de los números naturales es el mismo que 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 (ignorando los ceros iniciales) o 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 con el orden lexicográfico. El espacio en blanco de relleno en este contexto es un dígito "0" al final.

Cuando también se consideran números negativos, hay que invertir el orden para comparar números negativos. Esto no suele ser un problema para los humanos, pero puede serlo para las computadoras (probar el signo lleva algo de tiempo). Esta es una de las razones para adoptar la representación del complemento a dos para representar números enteros con signo en las computadoras.

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

Monoide de palabras

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 . Según esta definición, la palabra vacía ( ) es un prefijo de cada palabra, y cada palabra es un prefijo de sí misma (con w ); se debe tener cuidado si se deben excluir estos casos. ${\displaystyle \varepsilon }$ ${\displaystyle =\varepsilon }$

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 está vacío, entonces se tiene a < b bajo 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

Tenga en cuenta que, debido a la condición del prefijo en esta definición, donde es la palabra vacía. ${\displaystyle \varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,}$ ${\displaystyle \varepsilon }$

Si es un orden total en entonces también lo es el orden lexicográfico en las palabras de Sin embargo, en general no se trata de un buen orden , incluso si el alfabeto está bien ordenado. Por ejemplo, si A = { a , b } , el idioma { a ⁿ b | n ≥ 0, b > ε } no tiene ningún elemento menor en el orden lexicográfico: ... < aab < ab < b . ${\displaystyle \,<\,}$ ${\displaystyle A,}$ ${\displaystyle A.}$ ${\displaystyle A}$

Dado que muchas aplicaciones requieren un buen orden, a menudo se utiliza una variante del orden lexicográfico. Este buen orden, a veces llamado orden shortlex o orden cuasi lexicográfico , consiste en considerar primero las longitudes de las palabras (si length( a ) < length( b ) , entonces ), y, si las longitudes son iguales, utilizar el orden lexicográfico. Si el orden en A es un buen orden, lo mismo es válido para el orden shortlex. ^{[2] [3]} ${\displaystyle a<b}$

Productos cartesianos

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 totalmente ordenados. Un elemento de un producto cartesiano es una secuencia cuyo elemento ⁿ pertenece a para cada Como la evaluación del orden lexicográfico de las secuencias compara solo elementos que tienen el mismo rango en las secuencias, el orden lexicográfico se extiende a los productos cartesianos de conjuntos ordenados. ${\displaystyle E_{1}\times \cdots \times E_{n}}$ ${\displaystyle i}$ ${\displaystyle E_{i}}$ ${\displaystyle i.}$

En concreto, dados dos conjuntos parcialmente ordenados y el ${\displaystyle A}$ ${\displaystyle B,}$El orden lexicográfico en el producto cartesiano se define como ${\displaystyle A\times B}$ $${\displaystyle (a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ if and only if }}a<a^{\prime }{\text{ or }}\left(a=a^{\prime }{\text{ and }}b\leq b^{\prime }\right),}$$

El resultado es un orden parcial. Si y están totalmente ordenados , 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 . ${\displaystyle A}$ ${\displaystyle B}$

De manera similar, se puede definir el orden lexicográfico sobre 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 buenos órdenes 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 desde los números naturales hasta también conocido como el espacio de Cantor ) no está bien ordenado; el subconjunto de secuencias que tienen precisamente uno (es decir, { 100000..., 010000..., 001000..., ... } ) no tiene un elemento mínimo bajo el orden lexicográfico inducido por 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. ${\displaystyle \{0,1\},}$ ${\displaystyle \{0,1\}^{\omega }}$ ${\displaystyle 1}$ ${\displaystyle 0<1,}$

Funciones sobre un conjunto bien ordenado

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

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

Subconjuntos finitos

Los ordenamientos de los 3 subconjuntos de se representan como conjuntos de cuadrados rojos, secuencias crecientes (en azul), o por sus funciones indicadoras , convertidas en notación decimal (en gris). Los números grises son también el rango de los subconjuntos en todos los subconjuntos de numerados en orden colexicográfico, y comenzando desde 0. Los órdenes lexicográfico (lex) y colexicográfico (colex) están en la parte superior y los órdenes inversos correspondientes (rev) en la parte inferior. Se pasa de un orden a su orden inverso, ya sea leyendo de abajo hacia arriba en lugar de de arriba hacia abajo, o intercambiando los colores rojo y blanco. ${\displaystyle \{1,\ldots ,6\},}$ ${\displaystyle \{1,\ldots ,6\},}$

En combinatoria , a menudo hay que enumerar y, por tanto, ordenar los subconjuntos finitos de un conjunto dado. Para ello, se suele elegir un orden en . Luego, ordenar un subconjunto de 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 . ${\displaystyle S.}$ ${\displaystyle S.}$ ${\displaystyle S}$

En este contexto, generalmente se prefiere ordenar primero los subconjuntos por cardinalidad , como en el orden shortlex . Por lo tanto, en lo sucesivo, solo consideraremos órdenes en subconjuntos de cardinalidad fija.

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

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 (ver abajo) es a menudo 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 números naturales. Este no es el caso para el orden lexicográfico, ya que, con el orden lexicográfico, tenemos, por ejemplo, para cada ${\displaystyle n}$ ${\displaystyle 12n<134}$ ${\displaystyle n>2.}$

Órdenes grupales de Znorte

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

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

El orden lexicográfico también puede utilizarse para caracterizar todos los órdenes de grupo en ^{[4] [5]} De hecho, las formas lineales con coeficientes reales definen una función de en la 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 esta función induce un orden de grupo según el teorema de Robbiano, que establece que todo orden de grupo puede obtenerse de esta manera. ${\displaystyle \mathbb {Z} ^{n}.}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{n},}$ ${\displaystyle \mathbb {Z} ^{n}.}$

Más precisamente, dado un orden de grupo en , existen formas enteras y lineales con coeficientes reales, tales que la función inducida de en tiene las siguientes propiedades: ${\displaystyle \mathbb {Z} ^{n},}$ ${\displaystyle s\leq n}$ ${\displaystyle s}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{s}}$

• ${\displaystyle \varphi }$es inyectiva;
• El isomorfismo resultante de la imagen de es un isomorfismo de orden cuando la imagen está dotada del orden lexicográfico en ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \varphi }$ ${\displaystyle \mathbb {R} ^{s}.}$

Orden colexicográfico

Ordenamientos de las 24 permutaciones de {1,...,5} que son 5-ciclos (en azul). Los vectores de inversión (en rojo) de las permutaciones en orden colex están en orden revcolex , y viceversa.

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 está definido 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 orden lexicográfico no es muy significativa. Sin embargo, cuando se consideran secuencias crecientes, generalmente para subconjuntos de codificación, los dos órdenes difieren significativamente.

Por ejemplo, para ordenar las secuencias crecientes (o los conjuntos) de dos números 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 propiedad principal 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 .

Monomios

Al considerar polinomios , el orden de los términos no importa en general, ya que la adición 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 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, se debe satisfacer una condición adicional, a saber, que cada 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 . ${\displaystyle a<b{\text{ implies }}ac<bc,}$

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

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

Otra consiste en comparar primero los grados totales y luego resolver los conflictos utilizando el orden lexicográfico. Este orden no se utiliza mucho, ya que tanto el orden lexicográfico como el orden lexicográfico inverso de los grados tienen, en general, mejores propiedades.

El orden lexicográfico inverso de grado consiste también en comparar primero los grados totales y, en caso de igualdad de los grados totales, utilizar el orden colexicográfico inverso. Es decir, dados dos vectores exponenciales, se tiene si o $${\displaystyle [a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]}$$ $${\displaystyle a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},}$$ $${\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 esta ordenación, los monomios de grado uno tienen el mismo orden que los indeterminados correspondientes (no sería el caso 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. No es el caso 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 exponenciales 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 de grado inverso es que un polinomio homogéneo es múltiplo del menos indeterminado si y sólo si su monomio principal (su monomio mayor) es un múltiplo de este menos indeterminado.

Véase también

• Colación
• Orden de 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
• Ordenamiento lexicográfico en la notación de índice abstracto tensorial
• Rotación de cuerdas mínima lexicográficamente
• Orden de Leximin
• Línea larga (topología)
• Palabra de Lyndon
• Producto estrella , una forma diferente de combinar pedidos parciales
• Orden Shortlex
• Órdenes sobre el producto cartesiano de conjuntos totalmente ordenados

Referencias

1. Egbert Harzheim (2006). Conjuntos ordenados . Springer. Págs. 88-89. ISBN. 978-0-387-24222-4.
2. Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That (Reescritura de términos y todo eso) . Cambridge University Press. págs. 18-19. ISBN 978-0-521-77920-3.
3. Calude, Cristian (1994). Información y aleatoriedad. Una perspectiva algorítmica . Monografías de la EATCS sobre informática teórica. Springer-Verlag . p. 1. ISBN. 3-540-57456-5.Zbl 0922.68073  .
4. Robbiano, L. (1985). Ordenamiento de términos en el anillo de polinomios. En European Conference on Computer Algebra (pp. 513-517). Springer Berlin Heidelberg.
5. Weispfenning, Volker (mayo de 1987), "Órdenes admisibles y formas lineales", Boletín SIGSAM , 21 (2), Nueva York, NY, EE. UU.: ACM: 16–18, doi : 10.1145/24554.24557 , S2CID  10226875.

Enlaces externos

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