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

Определение

Пусть дано множество [math]~A=\{a_1\lt a_2\lt a_3\lt ...\lt a_k\}[/math] и [math]A^*=\bigcup^{\infty}_{i=0} A^i[/math], тогда после лексикографического упорядочивания элементов множества[math]~A^*[/math] любые два элемента (пусть [math]~x\lt 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\gt 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\lt n:x_j=y_j; x_n\lt y_n[/math]

Примеры

1. Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
2. Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.

Ссылки

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