Лексикографический порядок

Лексикографический порядок — отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом [math]\displaystyle{ \Sigma }[/math]. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

Определение

Слово [math]\displaystyle{ \alpha }[/math] предшествует слову [math]\displaystyle{ \beta }[/math] ([math]\displaystyle{ \alpha }[/math] < [math]\displaystyle{ \beta }[/math]), если

• либо первые [math]\displaystyle{ m }[/math] символов этих слов совпадают, а [math]\displaystyle{ m+1 }[/math]-й символ слова [math]\displaystyle{ \alpha }[/math] меньше (относительно заданного в [math]\displaystyle{ \Sigma }[/math] порядка) [math]\displaystyle{ m+1 }[/math]-го символа слова [math]\displaystyle{ \beta }[/math] (например, АБАК < АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
• либо слово [math]\displaystyle{ \alpha }[/math] является началом слова [math]\displaystyle{ \beta }[/math] (например, МАТЕМАТИК < МАТЕМАТИКА; см. конкатенация).

Примеры

• Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Например, следующие слова идут в лексикографическом порядке: А < АА < ААА < ААБ < ААВ < АБ < АВ < Б < … < ЯЯЯ.
• Естественный порядок на неотрицательных целых [math]\displaystyle{ n }[/math]-значных числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999).