Utente:Grasso Luigi/sandbox4/Ordine lessicografico

L'ordine lessicografico è un criterio di ordinamento di stringhe costituite da una sequenza di simboli per cui è già presente un ordine interno. La regola di ordinamento corrisponde a quella utilizzata nei dizionari, da cui deriva il nome, anche se è estesa ad un qualunque insieme di simboli.

Definizione

Un alfabeto finito totalmente ordinato di simboli è un insieme $\Sigma =\left(\delta _{1},\delta _{2},....\delta _{n}\right)$, dotato di un ordine totale $\delta _{1}<\delta _{2}<\,\ldots <\delta _{n}$.

Date due sequenze di simboli

$I=\delta _{i_{1}}\delta _{i_{2}}\ldots \delta _{i_{n}}$

$J=\delta _{j_{1}}\delta _{j_{2}}\ldots \delta _{j_{m}}$,

si dice che $I<J$ se esiste un numero $k\in \mathbb {N}$ per cui $\delta _{i_{1}}\delta _{i_{2}}\ldots \delta _{i_{k}}=\delta _{j_{1}}\delta _{j_{2}}\ldots \delta _{j_{k}}$ e vale una delle seguenti relazioni:

$\delta _{i_{k+1}}<\delta _{j_{k+1}}$

$k=n\land n<m$.

Algoritmo di confronto

La regola data sopra è equivalente al seguente algoritmo di confronto:

• si pone $n=1$
• si confrontano i simboli nella posizione n-esima della stringa:
  • se una delle due stringhe non possiede l'elemento n-esimo, allora è minore dell'altra e l'algoritmo termina
  • se entrambe le stringhe non possiedono l'elemento n-esimo, allora sono uguali e l'algoritmo termina
  • se i simboli sono uguali, si passa alla posizione successiva della stringa ($n\rightarrow n+1$)
  • se questi sono diversi, il loro ordine è l'ordine delle stringhe

L'ordine lessicografico sull'insieme prodotto

Data una famiglia di insiemi ${\mathcal {A}}=\left\{A_{1},\,A_{2},\,\ldots ,\,A_{n}\right\}$, con i rispettivi ordini totali $\left\{<_{1},\,<_{2},\,\ldots ,\,<_{n}\right\}$, l'ordine lessicografico dell'insieme prodotto

$A_{1}\times A_{2}\times \ldots \times A_{n}$

è dato da

$(a_{1},a_{2},\dots ,a_{n})<^{d}(b_{1},b_{2},\dots ,b_{n})\iff (\exists \ m>0)\ (\forall \ i<m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m})$.

Con questa regola ogni posizione della stringa può corrispondere a simboli e criteri di ordinamento diversi; per $A_{1}=A_{2}=\ldots =A_{n}=\Sigma$, con lo stesso ordine totale, si ottiene la definizione precedentemente data.

Proprietà

La relazione tra stringhe definita dall'insieme lessicografico è di ordine parziale stretto e gode pertanto della proprietà transitiva e asimmetrica.

Ordine colessicografico

Orderings of the 24 permutations of {1,...,4} that are pari. The inversion vectors (in red) of permutations in colex order are in revcolex order, and vice versa.

The colexicographic or colex order is a variant of the lexicographical order that is obtained by reading finite sequences from the right to the left instead of reading them from the left to the right. More precisely, whereas the lexicographical order between two sequences is defined by

Template:Math if Template:Math for the first Template:Math where Template:Math and Template:Math differ, the colexicographical order is defined by

Template:Math if Template:Math for the last Template:Math where Template:Math and Template:Math differ

In general, the difference between the colexicographical order and the lexicographical order is not very significant. However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly.

For example, for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by

Template:Math,

and the colexicographic order begins by

Template:Math.

The main property of the colexicographical order for increasing sequences of a given length is that every initial segment is finite. In other words, the colexicographical order for increasing sequences of a given length induces an order isomorphism with the natural numbers, and allows enumerating these sequences. This is frequently used in combinatorics, for example in the proof of the Kruskal–Katona theorem.

Monomi

In algebra, e particolarmente in algebra computazionale è fondamentale avere un ordinamento sui termini di un polinomio, ovvero un ordine monomiale; questo problema può essere risolto con una variante dell'ordine lessicografico. In pratica, dato un alfabeto ordinato di variabili $x_{1},x_{2},\ldots$ si possono ordinare tutti i monomi considerando dapprima l'esponente di $x_{1}$, quindi l'esponente di $x_{2}$ e così via, finché non si trova una differenza tra gli esponenti. A questo punto si considera minore il monomio per cui l'esponente è minore.

In simboli, se $\mathbf {a} =x_{1}^{a_{1}}x_{2}^{a_{2}}\ldots$ e $\mathbf {b} =x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots$, con $a_{i},b_{i}\in \mathbb {Z}$, sono due monomi, e $k$ è il minimo valore per cui $a_{k}\neq b_{k}$, allora $\mathbf {a} <\mathbf {b} \Leftrightarrow a_{k}<b_{k}$, e $\mathbf {a} >\mathbf {b} \Leftrightarrow a_{k}>b_{k}$.

Voci correlate

• Relazione binaria
• Ordine alfabetico
• Ordinamento sul grado totale