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

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

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

Слово a предшествует слову b (a<b), если первые m символов слов совпадают, а m+1 символ слова a меньше (относительно отношения порядка, заданного в \Sigma) m+1 символа слова b.

Примеры[править | править вики-текст]

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