Orden lexicográfico

Orden lexicográfico

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

Contenido

Definición matemática

Pares

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

\forall (a,b), (a',b') \in A \times B:
(a,b) \le_{A,B} (a',b') \ \Leftrightarrow \ a < a' \vee (a = a' \wedge b \leq b')

Si \le_A y \le_B son órdenes totales, \le_{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.

Cadenas de caracteres

Una aplicación más general del orden lexicográfico es al comparar cadenas de caracteres. Distinto al caso para los productos cartesianos n-arios mencionados arriba, las cadenas de caracteres no poseen longitud fija. Usando la misma idea de definición recursiva que para el caso anterior, ahora debemos considerar el que una secuencia puede ser más larga que la otra, y que por lo tanto termine de recorrerse mientras que todavía quedan caracteres en la otra.

La secuencia más corta a considerar será la cadena vacía \epsilon, es decir:

\forall b \in \Sigma^* : \epsilon \leq b

Así, la definición recursiva queda:

\forall [a_1 \dots a_m], [b_1 \dots b_n] \in \Sigma^* \backslash \{\epsilon\} : [a_1 \dots a_m] \leq [b_1 \dots b_n] \Leftrightarrow a_1 < b_1 \vee (a_1 = b_1 \wedge [a_2 \dots a_m] \leq [b_2 \dots b_n])

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 a1 = b1 = 1 y b2 = 3 < a2 = 9.
  • Los diccionarios son el ejemplo más conocido de ordenamiento lexicográfico. En este caso, no se hace distinción entre mayúsculas y minúsculas, y se considera por lo tanto que a=A, b=B, c=C, etc.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Orden lexicográfico — El orden lexicográfico es el que se utiliza para ordenar caracteres. Normalmente se diferencia entre letras mayúsculas y minúsculas, y además se consideran los números y los signos de puntuación. En los diccionarios se utiliza orden lexicográfico …   Enciclopedia Universal

  • Orden (desambiguación) — Orden puede adqurir varios significados en diferentes disciplinas. Puede referirse a: Contenido 1 Teoría de sistemas 2 Criterios de ordenación 3 Significados en diferentes ciencias 3.1 …   Wikipedia Español

  • Orden total — En matemáticas, un orden total, orden lineal, orden simple, o simplemente orden en un conjunto X es una relación binaria sobre X que es antisimétrica, transitiva, y total; esto es, si se denota una tal relación por ≤, lo siguiente vale para… …   Wikipedia Español

  • Teoría del orden — La teoría del orden es una rama de la matemática que estudia varias clases de relaciones binarias que capturan la noción intuitiva del orden matemático. Este artículo da una introducción detallada a este campo e incluye algunas de las… …   Wikipedia Español

  • OEIS — La Enciclopedia electrónica de secuencias de enteros (OEIS por sus siglas en inglés, de On Line Encyclopedia of Integer Sequences) es una base de datos que registra secuencias de números enteros. Está disponible libremente en Internet, en la… …   Wikipedia Español

  • Categoría — Ayuda:Categoría Saltar a navegación, búsqueda Atajo A:CATA:CAT Una categoría es una agrupación de páginas que comparten algún tema en común. En una analogía con el sistema de archivos de un computador, las categorías cumplen la misma función que… …   Wikipedia Español

  • Ayuda:Categoría — Atajo A:CATA:CAT Una categoría es una agrupación de páginas que comparten algún tema en común. En una analogía con el sistema de archivos de un computador, las categorías cumplen la misma función que un directorio. El proceso de incluir una… …   Wikipedia Español

  • Trie — Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A), que sirve para almacenar un conjunto de cadenas E en el que: Σ es el alfabeto sobre el que están definidas las cadenas; S, el conjunto de estados, cada uno de los cuales …   Wikipedia Español

  • Combinádico — En este artículo sobre matemáticas se detectaron los siguientes problemas: Necesita ser wikificado conforme a las convenciones de estilo de Wikipedia. Carece de fuentes o referencias que aparezcan en una fuente acreditada …   Wikipedia Español

  • Wikipedia:Política de categorías — Lo siguiente es una propuesta de política, convención, o proceso de Wikipedia. La propuesta puede aún estar en desarrollo, bajo discusión, o en el proceso de reunir consenso para la adopción. Por lo tanto las referencias o enlaces a esta página… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”