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

Материал из WikiGrapp
Версия от 16:49, 17 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Лексикографический порядок''' (''Lexicographic order'') - Порядок слов в словаре, опре...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Литература

[Словарь]