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

Лексикографический порядок (Lexicographic order) — Порядок слов в словаре, определяемый последовательностью букв алфавита. В более общем случае рассматривается множество [math]\displaystyle{ \,S }[/math], строго упорядоченное отношением [math]\displaystyle{ \,\lt }[/math]. Пусть для [math]\displaystyle{ \,n \gt 0 }[/math] имеется множество [math]\displaystyle{ \,T }[/math] [math]\displaystyle{ \,n }[/math]-кортежей [math]\displaystyle{ (x_{1}, x_{2}, \ldots, x_{n}) }[/math] с элементами [math]\displaystyle{ x_{j} \in S }[/math]. Тогда отношение упорядочения этих кортежей можно определить так, что [math]\displaystyle{ (x_{1}, x_{2}, \ldots, x_{n}) \lt (y_{1}, y_{2}, \ldots, y_{n}) }[/math] тогда и только тогда, когда [math]\displaystyle{ \,x_{1} \lt y_{1} }[/math]или существует некоторое [math]\displaystyle{ \,k }[/math], [math]\displaystyle{ 1 \leq k \leq n }[/math], для которого [math]\displaystyle{ \,x_{i} = y_{i} }[/math] при [math]\displaystyle{ 1 \leq i \lt k }[/math], и [math]\displaystyle{ \,x_{k} \lt y_{k} }[/math] Множество [math]\displaystyle{ \,T }[/math] лексикографически упорядочено, если кортежи расположены в соответствии с указанным отношением. Рассмотренное понятие можно обобщить для строк неодинаковой длины.

Литература

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.