== {{Определение |definition==Рассмотрим сравнение объектов, состоящих из элементов, на которых задан порядок. Если нам Пусть даны два объекта две последовательности <tex> ~P A = a_1 a_2 \dots a_n </tex> и <tex> ~Q B = b_1 b_2 \dots b_m </tex>, то Тогда последовательность <tex> ~P A </tex> '''лексикографически меньше, чем ''' (англ. ''lexicographically less'') последовательности <tex> ~Q B </tex>, если объект выполняется одно из двух условий:*<tex> ~P n < m </tex> является префиксом и при этом <tex> ~Q a_i = b_i </tex>, либо если первые для всех <tex> ~i \in [1 .. n] </tex> элементов объектов совпадают, а * <tex> \exists k\leqslant \min(n, m): a_k < b_k </tex> и при этом <tex> ~P_i \forall j : j < k ~Q_i a_j = b_j </tex>.}}
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''': '''function''' compare(A, B : '''list <T>'''): '''Ord''' <font color=green>// Возвращает "LT", если A < B, "GT", если A > B, или "EQ", если последовательности равны</font> '''for''' i = 1 '''to''' min(len(A), len(B)) '''if''' A[i] < B[i] <font color= Сравнение слов green> // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны</font> '''return''' LT '''if''' A[i] > B[i] <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font> '''return''' GT '''if''' len(A) < len(B) <font color=green>// А {{---}} префикс В, но не равна ей</font> '''return''' LT '''if''' len(A) > len(B) <font color=green>// В {{---}} префикс А, но не равна ей</font> '''return''' GT '''return''' EQ <font color=green>// Длины последовательностей и все элементы равны</font>Что же значит{{Определение|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''), что слово если для любых <tex> ~A i<j </tex> меньше слова выполняется неравенство <tex> ~B S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.}}Например, слово "сон" лексикографически меньше слова "сонный", так как вообще можно сравнивать оно является его префиксом. Слово "низ" лексикографически меньше слова?"нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
1. Слово <tex> ~A </tex> является префиксом слова <tex> ~B </tex>
2. Ни одно из слов не является префиксом другого, но существует <tex> i </tex> <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
Приведем псевдокод сравнения слов:== Примеры == function isEqual* Перестановки (A<font color=#c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, B : string<font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, так как <tex>4 < 6</tex>, то первая перестановка лексикографически меньше) for i {| cellpadding= 0 "4" style="margin-left: left; margin-right: left;" | [[Файл:Compareperm.. minpng]] |}* Сочетания (len(A)так как <tex>4 < 6</tex>, len(B)то первое сочетание лексикографически меньше) {| cellpadding="4" style="margin-left: left; margin- 1 //Длины равны, символы строк нумеруются с ноляright: left;" if (A| [[iФайл:Comparechoose.png] < B[i]) return <|} if (A* [[iкомбинаторные объекты|Разбиение на слагаемые] > B[i]) return (так как <tex> //Одна из строк является префиксом другой if (len(A) 4 < len(B)) return 9< if (len(A) /tex> len(B), то первое разбиение на слагаемые лексикографически меньше) return >{| cellpadding="4" style="margin-left: left; margin-right: left;"| [[Файл:Compare part.png]] return = //Длины строк и все символы равны|}
== Примеры ==# * Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<tex>000</tex>, <tex>001</tex>, <tex>002</tex>, <tex>003</tex>, <tex>004</tex>, <tex>005</tex>, …<tex>\dots</tex>, <tex>999</tex>).# * Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — {{---}} это, например, ААА<tex>AAA</tex>, <tex>AAB</tex>, ААБ<tex>AAC</tex>, <tex>AAD</tex>, <tex>\dots</tex>, <tex>ZZZ</tex>.* Эти слова тоже записаны в лексикографическом порядке: <tex>airport</tex>, ААВ<tex>duck</tex>, ААГ<tex>horse</tex>, …<tex>house</tex>, ЯЯЯ<tex>sleep</tex>. == См.также ==* [[Генерация комбинаторных объектов в лексикографическом порядке]]* [[Получение предыдущего объекта]]* [[Получение следующего объекта]]== Источники информации==*[http://en.wikipedia.org/wiki/Lexicographical_order Wikipedia {{---}} Lexicographical order]*[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 Википедия {{---}} Лексикографический порядок ] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]
