72
правки
Изменения
Нет описания правки
2. Длины слов равны, но <math>\mathcal {9} i </math> <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
Приведем псевдокод сравнения слов: function isEqual(A, B : string) if (len(A) < len(B)) return < if (len(B) < len(A)) return > for i = 0 .. len(A) - 1 //Длины равны, строки нумеруются с ноля if (A[i] < B[i]) return < if (A[i] > B[i]) return > //все символы равны return = == Генерация слов в лексикографическом порядке ==Попробуем сгенерировать все слова в лексикографическом порядке. Для этого воспользуемся рекурсией. Параметром для рекурсии будет служить префикс, который мы уже записали. Тогда если наш префикс уже длины <tex> L </tex> (которую мы хотим получить), то запишем получившееся слово, и выйдем из рекурсии. Если длина меньше, то будем приписывать по символу, в порядке от меньшего к большему и снова запускать рекурсию от нового префикса. Почему это будет работать? Ну давайте проверим определение: мы генерируем слова одинаковой длины, потому проверим пункт 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).
# Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.
== Ссылки ==
