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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 31: Строка 31:
  
 
* [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://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 Лексикографический порядок]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Комбинаторика ]]

Версия 23:28, 16 января 2012

Определение

Пусть нам дан алфавит [math] \Sigma [/math], на котором определен линейный порядок.

Говорят, что слово [math] ~A [/math] меньше слова [math] ~B [/math], если выполнено одно из следующих условий:

  1. Слово [math] ~A [/math] является префиксом слова [math] ~B [/math].
  2. Cуществует [math] 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 Сompare(A, B : string) // Возвращает "<" (если A < B), ">" (если A > B), или "=", (если строки равны)
   for i = 1 .. min(len(A), len(B))
        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] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math], где [math] S_i [/math] и [math] S_j [/math] слова с номерами [math] i [/math] и [math] j [/math]. Например, слово "сон" лексикографически меньше слова "сонный", так как оно является его префиксом. Слово "низ" лексикографически меньше слова "нос", поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.

Примеры

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

Ссылки