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