Изменения
Нет описания правки
{{Определение
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 ... \dots a_n </tex> и <tex> ~B = b_1 b_2 ... \dots b_m </tex> Тогда последовательность <tex> ~A </tex> '''лексикографически меньше''' (англ. ''lexicographically less'') последовательности <tex> ~B </tex>, если выполняется одно из двух условий:*<tex> n < m </tex> и при этом <tex> a_i = b_i </tex> для всех <tex>i \in [1; .. n] </tex> ,* <tex> \mathcal {9} exists k\leqslant \min(n, m): a_k < b_k </tex> и при этом <tex> \mathcal {8} forall j : j < k ~a_j = b_j </tex>.
}}
Приведем псевдокод сравнения последовательностей из элементов множества '''Т''':
'''function''' Сomparecompare(A, B : '''list <T>''') : '''Ord''' <font color=green>// Возвращает "LESSLT", если A < B, "MOREGT", если A > B, или "EQUALEQ", если последовательности равны</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''' LESSLT '''if''' A[i] > B[i] <font color=green> // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны</font> '''return''' MOREGT '''if''' len(A) < len(B) <font color=green>// А {{- --}} префикс В, но не равна ей.</font> '''return''' LESSLT '''if''' len(A) > len(B) <font color=green>// В {{--- }} префикс А, но не равна ей.</font> '''return''' MOREGT '''return''' EQUAL EQ <font color=green>// Длины последовательностей и все элементы равны</font>
{{Определение
|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''(lexicographical order)''), если для любых <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> общий префикс, записанных в фиксированной разрядной сетке (000, 001<font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, 002так как <tex>4 < 6</tex>, 003, 004, 005, …, 999то первая перестановка лексикографически меньше){| 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]] |}
== См. также ==* [[Генерация комбинаторных объектов в лексикографическом порядке]]* [[Получение предыдущего объекта]]* [[Получение следующего объекта]]== Источники информации==*[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 Википедия {{---}} Лексикографический порядок]*[http://en.wikipedia.org/wiki/Lexicographical_order Lexicographical order]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
