1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|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''' 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> 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> первый отличный элемент, так как <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>airport</tex>, <tex>duck</tex>, <tex>horse</tex>, <tex>house</tex>, <tex>sleep</tex>.
== См. также ==
* [[Генерация комбинаторных объектов в лексикографическом порядке]]
* [[Получение предыдущего объекта]]
* [[Получение следующего объекта]]
== Источники информации==
*[http://en.wikipedia.org/wiki/Lexicographical_order Wikipedia {{---}} Lexicographical order]
