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

Материал из WikiGrapp

Лексикографический порядок (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] лексикографически упорядочено, если кортежи расположены в соответствии с указанным отношением. Рассмотренное понятие можно обобщить для строк неодинаковой длины.

Литература

[Словарь]