Изменения

{{Определение|definition=Пусть дано множество даны две последовательности <mathtex>~A=a_1 a_2 \dots a_n </tex> и <tex> ~B = b_1 b_2 \{a_1dots b_m <a_2/tex> Тогда последовательность <a_3tex> ~A </tex> '''лексикографически меньше''' (англ.''lexicographically less'') последовательности <tex> ~B </tex>, если выполняется одно из двух условий:*<tex> n < m </tex> и при этом <tex> a_i = b_i </tex> для всех <tex>i \in [1 ..n] </tex>,* <tex> \exists k\leqslant \min(n, m): a_k\}< b_k </mathtex> и при этом <tex> \forall j : j <mathk ~a_j = b_j </tex>.}} Приведем псевдокод сравнения последовательностей из элементов множества '''Т''': '''function''' compare(A^*, B : '''list <T>'''): '''Ord''' <font color=\bigcup^{\infty}_{green>// Возвращает "LT", если A < B, "GT", если A > B, или "EQ", если последовательности равны</font> '''for''' i=0} 1 '''to''' min(len(A), len(B)) '''if''' A^[i] < B[i] <font color=green> /math>/ i-й элемент А меньше i-го элемента B, тогда после лексикографического упорядочивания элементов множествано префиксы длины i - 1 равны<math/font>~ '''return''' LT '''if''' A^*[i] > B[i] <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</mathfont> любые два элемента '''return''' GT '''if''' len(пусть A) <mathlen(B) <font color=green>~x// А {{---}} префикс В, но не равна ей<y; x,y \in /font> '''return''' LT '''if''' len(A^*; x) > len(B) <font color=\green>// В {x_1,x_2,...,x_{i_1---}\}; yпрефикс А, но не равна ей</font> '''return''' GT '''return''' EQ <font color=\green>// Длины последовательностей и все элементы равны</font>{{y_1Определение|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''),y_2если для любых <tex> i<j </tex> выполняется неравенство <tex> S_i<S_j </tex>,где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.}}Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом.Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.    == Примеры ==* Перестановки (<font color=#c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, <font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент,y_так как <tex>4 < 6</tex>, то первая перестановка лексикографически меньше){i_2| 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; x_j"| [[Файл:Compare part.png]] |} * Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<tex>000</tex>, <tex>001</tex>, <tex>002</tex>,y_j <tex>003</tex>, <tex>004</tex>, <tex>005</tex>, <tex>\in Adots</tex>, <tex>999</mathtex>) этого множества будут удовлетворять условиям:.* либо Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок {{---}} это, например, <tex>AAA<math/tex>~i_2, <tex>AAB</tex>, <tex>AAC</tex>, <tex>i_1AAD</mathtex> и , <mathtex>\forall j\le{i_1}:x_j=y_jdots</tex>, <tex>ZZZ</mathtex>.* либо Эти слова тоже записаны в лексикографическом порядке: <tex>airport<math/tex>, <tex>duck</tex>, <tex>horse</tex>\exists n\le{min(i_1,i_2)}:\forall j<n:x_j=y_j; x_ntex>house</tex>, <y_ntex>sleep</mathtex>. == См. также ==* [[Генерация комбинаторных объектов в лексикографическом порядке]]* [[Получение предыдущего объекта]]* [[Получение следующего объекта]]== Источники информации==*[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 Википедия {{---}} Лексикографический порядок ] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]