Лексикографический порядок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сравнение слов)
(Сравнение слов)
Строка 7: Строка 7:
 
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
 
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
  
1. Длина (количество элементов) слова <tex> ~A </tex> меньше длины слова <tex> ~B </tex>
+
1. Слово <tex> ~A </tex> является префиксом слова <tex> ~B </tex>
  
2. Длины слов равны, но <tex>\exists i </tex>  <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
+
2. Ни одно из слов не является префиксом другого, но <tex>\exists i </tex>  <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)
 
  function isEqual(A, B : string)
    if (len(A) < len(B))
+
    for i = 0 .. min(len(A), len(B)) - 1 //Длины равны, строки нумеруются с ноля
        return <
 
    if (len(B) < len(A))
 
        return >
 
    for i = 0 .. len(A) - 1 //Длины равны, строки нумеруются с ноля
 
 
         if (A[i] < B[i])
 
         if (A[i] < B[i])
 
             return <
 
             return <
 
         if (A[i] > B[i])
 
         if (A[i] > B[i])
 
             return >
 
             return >
     //все символы равны
+
     //Одна из строк является префиксом другой
     return =
+
    if (len(A) < len(B))
 +
        return <
 +
    if (len(A) > len(B))
 +
        return >
 +
     return = //Длины строк и все символы равны
  
 
== Генерация слов в лексикографическом порядке ==
 
== Генерация слов в лексикографическом порядке ==

Версия 03:04, 12 ноября 2011

Определение

Пусть дано линейно упорядоченное множество [math]~E=\{e_1\lt e_2\lt e_3\lt ...\lt e_k\}[/math] — алфавит. Словом назовем упорядоченное множество [math] ~S [/math] элементов алфавита [math] ~A [/math]. Тогда если на алфавите [math] A [/math] задан порядок, то порядок задан и на слове [math] ~S [/math]. Тогда говорят, что множество слов [math] ~A [/math] задано в лекcикографическом порядке, если для [math]\forall i \in A [/math] [math]\forall j \in A [/math] таких, что [math] i \lt j [/math] выполнено, что слово [math] ~A_i [/math] меньше, чем слово [math] ~A_j [/math].

Сравнение слов

Что же значит, что слово [math] ~A [/math] меньше слова [math] ~B [/math], и как вообще можно сравнивать слова?

Говорят, что слово [math] ~A [/math] меньше слова [math] ~B [/math], если:

1. Слово [math] ~A [/math] является префиксом слова [math] ~B [/math]

2. Ни одно из слов не является префиксом другого, но [math]\exists i [/math] [math] \ge 0 [/math] такое, что для всех [math] j \lt i [/math] выполнено неравенство [math] A_j = B_j [/math], а [math] A_i \lt B_i [/math]. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.

Приведем псевдокод сравнения слов:

function isEqual(A, B : string)
   for i = 0 .. min(len(A), len(B)) - 1 //Длины равны, строки нумеруются с ноля
        if (A[i] < B[i])
            return <
        if (A[i] > B[i])
            return >
    //Одна из строк является префиксом другой
    if (len(A) < len(B))
        return <
    if (len(A) > len(B))
        return >
    return = //Длины строк и все символы равны

Генерация слов в лексикографическом порядке

Попробуем сгенерировать все слова в лексикографическом порядке. Для этого воспользуемся рекурсией.

Параметром для рекурсии будет служить префикс, который мы уже записали. Тогда если наш префикс уже длины [math] L [/math] (которую мы хотим получить), то запишем получившееся слово, и выйдем из рекурсии. Если длина меньше, то будем приписывать по символу, в порядке от меньшего к большему и снова запускать рекурсию от нового префикса.

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

Пусть мы сейчас имеем префикс длины [math] i [/math] и все строки, начинающихся с префиксов меньших, чем наш уже выведены. Тогда согласно алгоритму мы будем приписывать меньшие символы, и достраивать при помощи рекурсии их до полных строк, то есть перебирать все строки с новым префиксом. А так как мы приписываем символы по увеличению, то все слова с меньшим префиксом мы заведомо переберем, следовательно слова будут в лексикографическом порядке.

Приведем псевдокод генерации:

procedure generate(s : string)
    if (len(s) == L) 
        write(s);
        exit;
    for i = 'a' .. 'z'
        generate(s + i)


Примеры

  1. Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
  2. Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.