Лексикографический порядок — различия между версиями
Gemin (обсуждение | вклад) |
Gemin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | == Определение == | ||
Пусть дано множество <math>~A=\{a_1<a_2<a_3<...<a_k\}</math> и <math>A^*=\bigcup^{\infty}_{i=0} A^i</math>, тогда после лексикографического упорядочивания элементов множества<math>~A^*</math> любые два элемента (пусть <math>~x<y; x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A</math>) этого множества будут удовлетворять условиям: | Пусть дано множество <math>~A=\{a_1<a_2<a_3<...<a_k\}</math> и <math>A^*=\bigcup^{\infty}_{i=0} A^i</math>, тогда после лексикографического упорядочивания элементов множества<math>~A^*</math> любые два элемента (пусть <math>~x<y; x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A</math>) этого множества будут удовлетворять условиям: | ||
* либо <math>~i_2>i_1</math> и <math>\forall j\le{i_1}:x_j=y_j</math> | * либо <math>~i_2>i_1</math> и <math>\forall j\le{i_1}:x_j=y_j</math> | ||
* либо <math>\exists n\le{min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</math> | * либо <math>\exists n\le{min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</math> | ||
| + | == Примеры == | ||
| + | # Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999). | ||
| + | # Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ. | ||
| + | == Ссылки == | ||
| + | * [http://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D0%BA%D1%81%D0%B8%D0%BA%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA Лексикографический порядок] | ||
Версия 07:21, 2 ноября 2010
Определение
Пусть дано множество и , тогда после лексикографического упорядочивания элементов множества любые два элемента (пусть ) этого множества будут удовлетворять условиям:
- либо и
- либо
Примеры
- Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
- Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.
