WikiSort.ru - Программирование

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

Определение

Слово ${\displaystyle \alpha }$ предшествует слову ${\displaystyle \beta }$ (${\displaystyle \alpha }$ < ${\displaystyle \beta }$ ), если

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

Примеры

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

Это заготовка статьи по алгебре. Вы можете помочь проекту, дополнив её.

Это заготовка статьи по лингвистике. Вы можете помочь проекту, дополнив её.

Для улучшения этой статьи желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.