Изменения

== {{Определение |definition==Пусть дано линейно упорядоченное множество даны две последовательности <tex>~A=\{a_1<a_2\dots a_n <a_3/tex> и <...<a_ktex> ~B = b_1 b_2 \}dots b_m </tex> - алфавит, Тогда последовательность <tex>~A^*</tex> назовем множество подпоследовательностей конечной длины '''лексикографически меньше''' (англ. ''lexicographically less'') последовательности <tex> ~B </tex>, если выполняется одно из алфавита двух условий:*<tex> A n < m </tex>, и при этом <tex>A^*a_i =b_i </tex> для всех <tex>i \bigcup^{\infty}_{i=0} A^iin [1 .. n] </tex>, тогда лексикографическим порядком на множестве * <tex>~A^*\exists k\leqslant \min(n, m): a_k < b_k </tex> назовем такой порядок, и при котором, элементы этом <tex>\forall j : j < k ~xa_j = b_j </tex>.}} Приведем псевдокод сравнения последовательностей из элементов множества '''Т''': '''function''' compare(A, B : '''list <T>'''): '''Ord''' <font color=green>// Возвращает "LT", если A <y; xB,y \in "GT", если A^*; x> B, или "EQ", если последовательности равны</font> '''for''' i =\{x_11 '''to''' min(len(A),x_2len(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,x_но префиксы длины i - 1 равны</font> '''return''' GT '''if''' len(A) < len(B) <font color=green>// А {{i_1---}\}; yпрефикс В, но не равна ей</font> '''return''' LT '''if''' len(A) > len(B) <font color=\green>// В {y_1,y_2,...,y_{i_2---}\}; x_jпрефикс А, но не равна ей</font> '''return''' GT '''return''' EQ <font color=green>// Длины последовательностей и все элементы равны</font>{{Определение|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''),y_j \in Aесли для любых <tex> i<j </tex> xвыполняется неравенство <tex>A^*S_i<S_j </tex>, то они удовлетворяют условиям:где <brtex>* либо S_i </tex>~i_2и <tex>i_1S_j </tex> и последовательности с номерами <tex>\forall j\le{i_1}:x_j=y_ji </tex>* либо и <tex>\exists n\le{\min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</tex>.}}Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.   

* Перестановки (<font color=# c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, <font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, так как <tex>4 < 6</tex>, то первая перестановка лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;" | [[Файл:Compareperm.png]] |}* Сочетания (так как <tex>4 < 6</tex>, то первое сочетание лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;"| [[Файл:Comparechoose.png]] |}* [[комбинаторные объекты|Разбиение на слагаемые]] (так как <tex>4 < 9</tex>, то первое разбиение на слагаемые лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;"| [[Файл:Compare part.png]] |} * Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<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 Википедия {{---}} Лексикографический порядок] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]