Lexicographic Order — Definition, Formula & Examples

Lexicographic order is a way of sorting sequences (like strings, tuples, or permutations) by comparing their elements one position at a time from left to right, just as words are ordered in a dictionary.

Given two sequences $a = (a_1, a_2, \ldots, a_n)$ and $b = (b_1, b_2, \ldots, b_m)$ over a totally ordered set, $a$ precedes $b$ in lexicographic order if there exists an index $k$ such that $a_i = b_i$ for all $i < k$ and $a_k < b_k$ , or if $a$ is a proper prefix of $b$ (i.e., $n < m$ and $a_i = b_i$ for all $i \leq n$ ).

How It Works

Start by comparing the first elements of two sequences. If they differ, the sequence with the smaller first element comes first. If they are equal, move to the second elements and repeat. Continue until you find a position where the elements differ or one sequence runs out. A shorter sequence that matches the beginning of a longer one is placed first. This process produces a total order on any finite set of sequences over an ordered alphabet.

Worked Example

Problem: Sort the 3-element permutations (2, 1, 3), (1, 3, 2), (1, 2, 3), and (2, 1, 1) into lexicographic order.

Step 1: Compare first elements. Two sequences start with 1 and two start with 2. Sequences starting with 1 come before those starting with 2.

1 < 2

Step 2: Among the sequences starting with 1, compare second elements: (1, 2, 3) has second element 2 and (1, 3, 2) has second element 3. Since 2 < 3, (1, 2, 3) comes first.

(1, 2, 3) < (1, 3, 2)

Step 3: Among the sequences starting with 2, both have second element 1, so compare third elements: (2, 1, 1) has 1 and (2, 1, 3) has 3. Since 1 < 3, (2, 1, 1) comes first.

(2, 1, 1) < (2, 1, 3)

Answer: The sorted order is: (1, 2, 3), (1, 3, 2), (2, 1, 1), (2, 1, 3).

Why It Matters

Lexicographic order is the standard method for systematically generating and enumerating permutations and combinations in combinatorics and algorithm design. It appears in computational problems ranging from string sorting to constraint satisfaction, and it underlies the comparison operators for strings and tuples in most programming languages.

Common Mistakes

Mistake: Comparing sequences by summing or globally evaluating their elements instead of comparing position by position.

Correction: Always compare left to right, one position at a time. For example, (1, 9) comes before (2, 0) even though 1 + 9 > 2 + 0, because the first element 1 < 2.