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 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 varias variantes y generalizaciones del ordenamiento lexicográfico. Una variante se aplica a secuencias de diferentes longitudes comparando las longitudes de las secuencias antes de considerar sus elementos.

Otra variante, muy 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 les 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 utilizadas en algún idioma) tienen un ordenamiento convencional, utilizado en diccionarios y enciclopedias , que depende del ordenamiento subyacente del alfabeto de símbolos utilizados 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 dos símbolos cualesquiera a y b en A que no sean el mismo símbolo, a < b o b < a .

Las palabras de A son secuencias finitas de símbolos de A , incluidas 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 sin ningún símbolo. El orden lexicográfico del 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 la primer lugar i donde las dos palabras difieren ( 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 más pequeño que cada elemento de A ) al final hasta que las palabras tengan la misma longitud, y luego las palabras se comparado como en el caso anterior.

Sin embargo, en combinatoria , se utiliza frecuentemente 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 a veces se denomina orden shortlex .

En orden lexicográfico, la palabra "Thomas" aparece antes de "Thompson" porque primero se diferencian en la quinta letra ('a' y 'p'), y la letra 'a' viene antes de la letra 'p' en el alfabeto. Debido a 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, cada secuencia decreciente de palabras de longitud n es finita (o de manera equivalente, 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 numéricos y fechas.

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

Uno de los inconvenientes del sistema de numeración romana es que no siempre es inmediatamente obvio cuál de dos números es el menor. Por otro lado, con la notación posicional del sistema de numeración hindú-árabe , 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 si el número de dígitos es el mismo y el primero El dígito (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, se comparan las partes a la derecha del punto decimal con el orden lexicográfico. El relleno 'en blanco' 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 la señal lleva algún tiempo). Ésta es una de las razones para adoptar la representación en complemento a dos para representar enteros con signo en las computadoras.

Otro ejemplo de uso del orden lexicográfico fuera del diccionario 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 de las secuencias de caracteres que representan fechas coincide con el orden cronológico : una fecha CE anterior es más pequeña en el orden lexicográfico que una fecha posterior hasta el año 9999. Este orden de fechas permite realizar una clasificación computarizada de las fechas. más fácil al evitar la necesidad de un algoritmo de clasificación separado.

monoide de palabras

El monoide de las 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 quieren 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 xey de A tales que

x < y

a = uxv

b = uyw

Observe que, debido a la condición del prefijo en esta definición, dónde está la palabra vacía. ${\displaystyle \varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,}$ ${\displaystyle \varepsilon }$

Si hay un orden total, también lo es el orden lexicográfico de las palabras de. Sin embargo, en general, este no es 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 el menor elemento en el orden lexicográfico: ... < aab < ab < b . ${\displaystyle \,<\,}$ ${\displaystyle A,}$ ${\displaystyle A.}$ ${\displaystyle A}$

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 longitud( a ) < longitud( b ) , entonces ) y, si las longitudes son iguales, utilizar el orden lexicográfico. . Si el orden en A es un orden bueno, lo mismo ocurre con 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 a cuyo ^ésimo elemento pertenece para cada. Como al evaluar el orden lexicográfico de las secuencias se comparan sólo los 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.}$

Específicamente, dados dos conjuntos parcialmente ordenados y el ${\displaystyle A}$ ${\displaystyle B,}$El orden lexicográfico del 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 tanto, una extensión lineal de su orden de producto . ${\displaystyle A}$ ${\displaystyle B}$

Se puede definir de manera similar 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 contables (por definición, el conjunto de funciones desde los números naturales hasta el también conocido como 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 desde un conjunto bien ordenado hasta un conjunto totalmente ordenado pueden identificarse con secuencias indexadas por elementos de. Por lo tanto, pueden ordenarse por el orden lexicográfico, y para dos de esas funciones , 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

Ordenamientos de los 3 subconjuntos representados como conjuntos de cuadrados rojos, secuencias crecientes (en azul), o por sus funciones indicadoras , convertidas a notación decimal (en gris). Los números grises también son el rango de los subconjuntos en todos los subconjuntos 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 correspondientes órdenes inversos (rev) en la parte inferior. Se pasa de un orden a su orden inverso, ya sea leyendo de abajo hacia arriba en lugar de arriba-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 lo tanto, ordenar los subconjuntos finitos de un conjunto dado. Para ello, normalmente se elige un orden en Entonces, ordenar un subconjunto de es equivalente a convertirlo en una secuencia creciente. El orden lexicográfico de las secuencias resultantes induce así un orden de 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, a continuación consideraremos sólo órdenes sobre subconjuntos de cardinales fijos.

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

Órdenes de grupo de Z n

Sea el grupo abeliano libre de rango cuyos elementos son secuencias de números enteros, y la operación es la suma . Un orden de grupo 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 grupal en ${\displaystyle \mathbb {Z} ^{n}.}$

El orden lexicográfico también puede usarse para caracterizar todos los órdenes de grupos en ^{[4] [5]} De hecho, las formas lineales con coeficientes reales definen un mapa desde dentro que es inyectivo si las formas son linealmente independientes (también puede ser inyectivo si el los formularios son dependientes, ver más abajo). El orden lexicográfico en la imagen de este mapa induce un orden de grupo según el teorema de Robbiano: 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, existen formas enteras y lineales con coeficientes reales, de modo que el mapa inducido desde dentro 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 inyectivo;
• el isomorfismo resultante de a la imagen de es un isomorfismo de orden cuando la imagen está equipada con el 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 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 está definido por

a ₁ a ₂ ... a _k < ^lex b ₁ b ₂ ... b _k si a _i < b _i para la primera 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 la última 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, normalmente para codificar subconjuntos, los dos órdenes difieren significativamente.

Por ejemplo, para ordenar las secuencias crecientes (o 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 principal propiedad del orden colexicográfico para secuencias crecientes de una longitud determinada es que cada segmento inicial es finito. En otras palabras, el orden colexicográfico para secuencias crecientes de una longitud determinada induce un isomorfismo de orden con los números naturales y permite enumerar estas secuencias. Esto se utiliza con frecuencia 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, pues 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 monomio , 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 cumplir una condición adicional: 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 . ${\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, por tanto, la restricción de un orden monomial de (ver arriba § Órdenes grupales 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. Históricamente, es el primero que se utilizó para definir las bases de Gröbner y, a veces, se le llama 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 el total de grados , y luego resolver los conflictos utilizando el orden lexicográfico. Este orden no se utiliza mucho, ya que el orden lexicográfico o el orden lexicográfico inverso en grados tienen generalmente mejores propiedades.

El orden lexicográfico inverso de grados consiste también en comparar primero el total de grados y, en caso de igualdad de los grados totales, utilizar el orden lexicográfico inverso. Es decir, dados dos vectores exponentes, se tiene

$${\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 este ordenamiento, los monomios de grado uno tienen el mismo orden que los indeterminados correspondientes (este 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. Este no es el caso con más variables. Por ejemplo, para vectores exponentes de monomios de grado dos en tres variables, se tiene para el grado 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 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 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.

Ver también

• 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 para encontrar un elemento lexicográficamente máximo.
• Topología de orden lexicográfico en el cuadrado unitario.
• Orden lexicográfico en notación de índice abstracto tensorial
• Rotación de cadenas lexicográficamente mínima
• orden leximina
• Línea larga (topología)
• palabra 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 . Saltador. págs. 88–89. ISBN 978-0-387-24222-4.
2. Franz Baader; Tobías Nipkow (1999). Reescritura de términos y todo eso . Prensa de la Universidad de Cambridge. 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 . pag. 1.ISBN _ 3-540-57456-5. Zbl  0922.68073.
4. Robbiano, L. (1985). Ordenamiento de términos en el anillo polinomial. En Conferencia europea sobre álgebra informática (págs. 513-517). Springer Berlín Heidelberg.
5. Weispfenning, Volker (mayo de 1987), "Órdenes admisibles y formas lineales", Boletín SIGSAM , Nueva York, NY, EE. UU.: ACM, 21 (2): 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