Lexicographic Order

software-engineering

Definition

Lexicographic Order (Tuples/Sequences)

Lexicographical order (or dictionary order) is a generalization of the standard ordering of words to sequences or tuples of elements from an ordered set.

Let $(\Sigma ,<)$ be a strictly ordered set (e.g., integers, characters). Let $A=(a_1,a_2,\dots ,a_m)$ and $B=(b_1,b_2,\dots ,b_n)$ be two finite sequences in ${\Sigma }^{\ast }$.

We say that $A$ is lexicographically smaller than $B$ ($A{<}_{lex}B$) if and only if one of the following holds:

1. Strict Prefix: $A$ is a proper prefix of $B$.
   $m<n\wedge \forall i\in \{1,\dots ,m\},a_i=b_i$
2. First Mismatch: At the first position $k$ where the sequences differ, the element in $A$ is smaller than the element in $B$.
   $\exists k\in \{1,\dots ,\min (m,n)\}:(a_k<b_k)\wedge (\forall i<k,a_i=b_i)$

Recursive Definition:
For sequences defined by a head ($h$) and tail ($T$), i.e., $A=h_A::T_A$, the order is defined recursively:

$$A{<}_{lex}B⟺\{\begin{array}{ll}\text{True}& \text{if }A=ϵ\wedge B\ne ϵ(\text{Empty is smallest})\\ \text{False}& \text{if }B=ϵ\\ \text{True}& \text{if }{h}_A<h_B\\ \text{False}& \text{if }{h}_B<h_A\\ T_A{<}_{lex}{T}_B& \text{if }{h}_A=h_B\end{array}$$

• Intuition: It behaves exactly like a dictionary. To compare two words, you look at the first letter. If they differ, the word with the “smaller” (earlier) letter comes first, regardless of what follows. If they match, you discard the first letter and compare the rest. If one word runs out of letters (is a prefix) while the other still has letters, the shorter one comes first.
• Significance: The position of an element determines its weight. The index $k=1$ is infinitely more significant than $k=100$.

Examples

1. Example (Mismatch Dominates Magnitude):
   • $T_1:=(1,1000)$
   • $T_2:=(2,0)$
   • $T_1{<}_{lex}{T}_2$. Even though $1000\gg 0$, the decision is made at the first index ($1<2$).
2. Example (Prefix Rule):
   • $T_1:=(1,2)$
   • $T_2:=(1,2,0)$
   • $T_1{<}_{lex}{T}_2$. The first two elements match, but $T_1$ runs out of elements first (length $2<3$).
3. Example (Empty Tuple):
   • $T_1:=()$
   • $T_2:=(5)$
   • $T_1{<}_{lex}{T}_2$. The empty tuple is the “smallest” element in the set of all sequences.
4. Example (Standard Tie-Breaking):
   • $T_1:=(3,4,1)$
   • $T_2:=(3,4,8)$
   • $T_1{<}_{lex}{T}_2$. Indices 1 and 2 match ($3=3,4=4$). The comparison happens at index 3 ($1<8$).