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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая Medvednikita (обсуждение | вклад) в 13:34, 22 ноября 2021 (отмена правки 116037949 участника JekaBomb (обс.)). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску

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

Определение

Слово предшествует слову ( < ), если

  • либо первые символов этих слов совпадают, а -й символ слова меньше (относительно заданного в порядка) -го символа слова (например, АБАК < АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
  • либо слово является началом слова (например, МАТЕМАТИК < МАТЕМАТИКА; см. конкатенация).

Примеры

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