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

Определение

Пусть дано линейно упорядоченное множество [math]~E=\{e_1\lt e_2\lt e_3\lt ...\lt e_k\}[/math] - алфавит. Словом назовем упорядоченное множество [math] ~S [/math] элементов алфавита [math] ~A [/math]. Тогда если на алфавите [math] A [/math] задан порядок, то порядок задан и на слове [math] ~S [/math]. Тогда говорят, что множество слов [math] ~A [/math] задано в лекcикографическом порядке, если для [math]\mathcal {8} i \in A [/math] [math]\mathcal {8} j \in A [/math] таких, что [math] i \lt j [/math] выполнено, что слово [math] ~A_i [/math] меньше, чем слово [math] ~A_j [/math].

Сравнение слов

Что же значит, что слово [math] ~A [/math] меньше слова [math] ~B [/math], и как вообще можно сравнивать слова?

Говорят, что слово [math] ~A [/math] меньше слова [math] ~B [/math], если:

1. Длина (количество элементов) слова [math] ~A [/math] меньше длины слова [math] ~B [/math]ю

2. Длины слов равны, но [math]\mathcal {9} i [/math] [math] \ge 0 [/math] такое, что для всех [math] j \lt i [/math] выполнено неравенство [math] A_j = B_j [/math], а [math] A_i \lt B_i [/math]. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.

Примеры

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