Русская Википедия:Лексикографический порядок
Материал из Онлайн справочника
Лексикографический порядок — отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом <math>\Sigma</math>. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.
Определение
Слово <math>\alpha</math> предшествует слову <math>\beta</math> (<math>\alpha</math> ≺ <math>\beta</math>), если
- либо первые <math>m</math> символов этих слов совпадают, а <math>m+1</math>-й символ слова <math>\alpha</math> меньше (относительно заданного в <math>\Sigma</math> порядка) <math>m+1</math>-го символа слова <math>\beta</math> (например, АБАК ≺ АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
- либо слово <math>\alpha</math> является началом слова <math>\beta</math> (например, МАТЕМАТИК ≺ МАТЕМАТИКА; Шаблон:Comment конкатенация).
Примеры
- Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Например, следующие слова идут в лексикографическом порядке: А ≺ АА ≺ ААА ≺ ААБ ≺ ААВ ≺ АБ ≺ АВ ≺ Б ≺ … ≺ ЯЯЯ.
- Естественный порядок на неотрицательных целых <math>n</math>-значных числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999).
Шаблон:Ling-stub Шаблон:Prog-stub Шаблон:Rq