Лексикографический порядок

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Лексикографический порядок — отношение линейного порядка на множестве кортежей \Sigma^*; \Sigma — упорядоченный алфавит. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

Кортеж a предшествует кортежу b (a<b), если для некоторого неотрицательного целого числа s первые s членов кортежей a и b совпадают, а (s+1)-й член кортежа a меньше соответствующего члена последовательности b. Если один кортеж является префиксом другого, то более короткий идёт раньше.

[править] Примеры

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


Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Участие
Печать/экспорт
Инструменты
На других языках