Изменения

== {{Определение |definition==Пусть дано линейно упорядоченное множество даны две последовательности <tex>~EA =a_1 a_2 \{e_1<e_2<e_3<...<e_k\}dots a_n </tex> {{---}} алфавит. Словом назовем упорядоченное множество и <tex> ~S B = b_1 b_2 \dots b_m </tex> элементов алфавита Тогда последовательность <tex> ~A </tex>'''лексикографически меньше''' (англ. Тогда если на алфавите ''lexicographically less'') последовательности <tex> A ~B </tex> задан порядок, то порядок задан и на слове если выполняется одно из двух условий:*<tex> ~S n < m </tex>. Тогда говорят, что множество слов и при этом <tex> ~A a_i = b_i </tex> задано в лекcикографическом порядке, если для любого всех <tex> i \in A [1 .. n] </tex> и любого ,* <tex> j \in A </tex> такихexists k\leqslant \min(n, что <tex> i m): a_k < j b_k </tex> выполнено, что слово и при этом <tex> ~A_i </tex> меньше, чем слово \forall j : j <tex> k ~A_j 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) <texfont color=green> ~P // В {{---}} префикс А, но не равна ей</texfont> и '''return''' GT '''return''' EQ <texfont color=green> ~Q // Длины последовательностей и все элементы равны</texfont>{{Определение|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''), то если для любых <tex> ~P i<j </tex> меньше, чем выполняется неравенство <tex> ~Q S_i<S_j </tex>, если объект где <tex> ~P S_i </tex> является префиксом и <tex> ~Q S_j </tex>, либо если первые последовательности с номерами <tex> ~i </tex> элементов объектов совпадают, а и <tex> ~P_i < ~Q_i j </tex>.}}Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.

2. Ни одно из слов не является префиксом другого, но == Примеры ==* Перестановки (<texfont color=#c355a0>\exists i '''светло-фиолетовым выделен'''</texfont> общий префикс, <texfont color=#992574> \ge 0 '''темно-фиолетовым'''</texfont> такоепервый отличный элемент, что для всех так как <tex> j 4 < i 6</tex> выполнено неравенство , то первая перестановка лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;" | [[Файл:Compareperm.png]] |}* Сочетания (так как <tex> A_j = B_j 4 < 6</tex>, а то первое сочетание лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;"| [[Файл:Comparechoose.png]] |}* [[комбинаторные объекты|Разбиение на слагаемые]] (так как <tex> A_i 4 < B_i 9</tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а то первое разбиение на алфавите задан строгий порядокслагаемые лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;"| [[Файл:Compare part.png]] |}

Приведем псевдокод сравнения слов: function isEqual* Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (A<tex>000</tex>, <tex>001</tex>, <tex>002</tex>, <tex>003</tex>, <tex>004</tex>, <tex>005</tex>, <tex>\dots</tex>, B : string<tex>999</tex>). for i = 0 * Порядок слов в словаре.Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. min(len(A)Тогда лексикографический порядок {{---}} это, например, <tex>AAA</tex>, <tex>AAB</tex>, <tex>AAC</tex>, len(B)) - 1 <tex>AAD</tex>, <tex>\dots</Длины равныtex>, строки нумеруются с ноля if (A[i] < B[i]) return tex>ZZZ< if (A[i] /tex> B[i]). return * Эти слова тоже записаны в лексикографическом порядке: <tex> airport</tex>, <tex>duck</Одна из строк является префиксом другой if (len(A) tex>, < len(B)) return tex>horse< if (len(A) /tex> len(B)) return , <tex> return = house</tex>, <tex>sleep</Длины строк и все символы равныtex>.