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

Лексикографический порядок — это порядок, в котором выстроены слова, например, в орфографических и русско-английских словарях.

Лексикографический порядок может быть введен на множестве слов (упорядоченных последовательностей элементов) над любым множеством, на котором уже введен строгий линейный порядок.

Пусть на множестве $X$ введен строгий линейный порядок $\prec$. Введем отношение $\prec_{lex}$ на множестве $X^* = \{(x_1, x_2, ..., x_k) | k\in\mathbb{N}, x_i\in X\}$ всех слов над множеством $X$. Пусть $\widetilde x^k = (x_1, ..., x_k)\in X^*$, $\widetilde y^l = (y_1, ..., y_l)\in X^*$, $\widetilde x^k\neq \widetilde y^l$ и $k\leq l$.

Будем говорить, что $\widetilde x^k \prec_{lex} \widetilde y^l$, если 1) существует такой индекс $t$, $1\leq t \leq k$, что $x_i = y_i$, $i=\overline{1,t-1}$, и $x_t\prec y_t$, или 2) $k < l$ и $x_i = y_i$, $i=\overline{1,k}$. В противном случае $\widetilde y^l \prec_{lex} \widetilde x^k$.

Замечание

На множестве слов одинаковой длины определение лексикографического порядка упростилось бы и приняло бы вид: $\widetilde x^k \prec_{lex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{1,t-1}, x_t\prec y_t$.

Рис. 1. Слова сравниваются по первой различающейся букве: [math]\displaystyle{ b \lt c }[/math], поэтому [math]\displaystyle{ abc \lt acb }[/math]. Если одно слово — начало другого, короткое идёт раньше: [math]\displaystyle{ ab \lt abc }[/math].

Выпишем все возможные перестановки чисел \{1, 2, 3, 4\}, выстроенные в лексикографическом порядке:

[math]\displaystyle{ \begin{array}{c} 1 2 3 4\\ 1 2 4 3\\ 1 3 2 4\\ 1 3 4 2\\ 1 4 2 3\\ 1 4 3 2\\ 2 1 3 4\\ 2 1 4 3\\ 2 3 1 4\\ 2 3 4 1\\ 2 4 1 3\\ 2 4 3 1\\ 3 1 2 4\\ 3 1 4 2\\ 3 2 1 4\\ 3 2 4 1\\ 3 4 1 2\\ 3 4 2 1\\ 4 1 2 3\\ 4 1 3 2\\ 4 2 1 3\\ 4 2 3 1\\ 4 3 1 2\\ 4 3 2 1\\ \end{array} }[/math]

Заметим, что здесь мы привели только перестановки — последовательности из различных символов. Если мы захотим выписать все слова в данном алфавите, их окажется гораздо больше.

Отметим также, что существует еще так называемый антилексикографический порядок. Он не является обратным лексикографическому порядку бинарным отношением. Список всех перестановок $n$ чисел в антилексикографическом порядке может быть получен следующим образом: сначала нужно выстроить все такие перестановки в лексикографическом порядке, а затем развернуть список в обратном порядке и развернуть каждое слово, описывающее перестановку. Такой порядок может быть полезен, например, для словаря окончаний.

Используя те же обозначения и договоренности, что и при введении лексикографического порядка, антилексикографический порядок можно определить следующим образом: Будем говорить, что $\widetilde y^l \prec_{alex} \widetilde x^k$, если

1) существует такой индекс $t$, \mbox{$1\leq t \leq k$}, что $x_{k-i+1} = y_{l-i+1}$, $i=\overline{1,t-1}$ и $x_{k-t+1}\prec y_{l-t+1}$,

или 2) $k < l$ и $x_{k-i+1} = y_{l-i+1}$, $i=\overline{1,k}$. В противном случае $\widetilde y^l \prec_{alex} \widetilde x^k$.

Замечание

На множестве слов одинаковой длины определение приняло бы следующий вид: $\widetilde x^k \prec_{alex} \widetilde y^k \Leftrightarrow \exists t\in\{1,...,k\}: x_i = y_i, i=\overline{t+1,k}, y_t\prec x_t$.

Приведем все возможные перестановки чисел $\{1, 2, 3, 4\}$, выстроенные в антилексикографическом порядке:

[math]\displaystyle{ \begin{array}{c} 1 2 3 4\\ 2 1 3 4\\ 1 3 2 4\\ 3 1 2 4\\ 2 3 1 4\\ 3 2 1 4\\ 1 2 4 3\\ 2 1 4 3\\ 1 4 2 3\\ 4 1 2 3\\ 2 4 1 3\\ 4 2 1 3\\ 1 3 4 2\\ 3 1 4 2\\ 1 4 3 2\\ 4 1 3 2\\ 3 4 1 2\\ 4 3 1 2\\ 2 3 4 1\\ 3 2 4 1\\ 2 4 3 1\\ 4 2 3 1\\ 3 4 2 1\\ 4 3 2 1\\ \end{array} }[/math]

Лексикографический и антилексикографический порядки являются отношениями строгого линейного порядка.

Конспект: Дискретная математика