Изменения

== {{Определение |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икографическом порядке, если для всех <mathtex>\mathcal {8} i \in A [1 .. n] </mathtex> ,* <mathtex>\mathcal {8} j exists k\leqslant \in A </math> таких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) <font color=green>// В {{---}} префикс А, но не равна ей</font> '''return''' GT '''return''' EQ <font color=green>// Длины последовательностей и все элементы равны</font>Что же значит{{Определение|definition=Последовательности записаны в '''лексикографическом порядке''' (англ. ''lexicographical order''), что слово если для любых <tex> ~A i<j </tex> меньше слова выполняется неравенство <tex> ~B S_i<S_j </tex>, где <tex> S_i </tex> и <tex> S_j </tex> последовательности с номерами <tex> i </tex> и <tex> j </tex>.}}Например, слово "сон" лексикографически меньше слова "сонный", так как вообще можно сравнивать оно является его префиксом. Слово "низ" лексикографически меньше слова?"нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.

Приведем псевдокод сравнения слов:== Примеры == function isEqual* Перестановки (A<font color=#c355a0>'''светло-фиолетовым выделен'''</font> общий префикс, <font color=#992574>'''темно-фиолетовым'''</font> первый отличный элемент, так как <tex>4 < 6</tex>, B то первая перестановка лексикографически меньше){| cellpadding="4" style="margin-left: left; margin-right: left;" | [[Файл: string)Compareperm.png]] |} if (len* Сочетания (A) так как < len(B)) return tex>4 < if (len(B) 6< len(A)/tex>, то первое сочетание лексикографически меньше) return > for i {| cellpadding="4" style= 0 .. len(A) "margin-left: left; margin- 1 //Длины равны, строки нумеруются с ноляright: left;" if (A| [[iФайл:Comparechoose.png] < B[i]) return <|} if (A* [[iкомбинаторные объекты|Разбиение на слагаемые]] (так как <tex>4 < 9</tex> B[i], то первое разбиение на слагаемые лексикографически меньше) return >{| cellpadding="4" style="margin-left: left; margin-right: left;" //все символы равны| [[Файл:Compare part.png]] return =|}

== Генерация * Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (<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>.

Параметром для рекурсии будет служить префикс, который мы уже записали== См. Тогда если наш префикс уже длины <tex> L <также ==* [[Генерация комбинаторных объектов в лексикографическом порядке]]* [[Получение предыдущего объекта]]* [[Получение следующего объекта]]== Источники информации==*[http://tex> (которую мы хотим получить), то запишем получившееся слово, и выйдем из рекурсии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 Википедия {{---}} Лексикографический порядок ]

Почему это будет работать? Ну давайте проверим определение[[Категория: мы генерируем слова одинаковой длины, потому проверим пункт 2.Дискретная математика и алгоритмы]]

Пусть мы сейчас имеем префикс длины <tex> i </tex> и все строки, начинающихся с префиксов меньших, чем наш уже выведены. Тогда согласно алгоритму мы будем приписывать меньшие символы, и достраивать при помощи рекурсии их до полных строк, то есть перебирать все строки с новым префиксом. А так как мы приписываем символы по увеличению, то все слова с меньшим префиксом мы заведомо переберем, следовательно слова будут в лексикографическом порядке.  Приведем псевдокод генерации[[Категория: procedure generate(s : string) if (len(s) == L) write(s); exit; for i = 'a' .. 'z' generate(s + i)  == Примеры ==# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).# Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.== Ссылки ==Комбинаторика ]]