Что такое лексикографический порядок
Перейти к содержимому

Что такое лексикографический порядок

  • автор:

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

Тогда последовательность [math] ~A [/math] лексикографически меньше (англ. lexicographically less) последовательности [math] ~B [/math] , если выполняется одно из двух условий:

Приведем псевдокод сравнения последовательностей из элементов множества Т:

function compare(A, B : list ): Ord // Возвращает "LT", если A < B, "GT", если A >B, или "EQ", если последовательности равны for i = 1 to min(len(A), len(B)) if A[i] < B[i] // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны return LT if A[i] > B[i] // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны return GT if len(A) < len(B) // А — префикс В, но не равна ей return LT if len(A) > len(B) // В — префикс А, но не равна ей return GT return EQ // Длины последовательностей и все элементы равны 
Определение:
Последовательности записаны в лексикографическом порядке (англ. lexicographical order), если для любых [math] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math] , где [math] S_i [/math] и [math] S_j [/math] последовательности с номерами [math] i [/math] и [math] j [/math] .

Например, слово «сон» лексикографически меньше слова «сонный», так как оно является его префиксом. Слово «низ» лексикографически меньше слова «нос», поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.

Примеры

  • Перестановки ( светло-фиолетовым выделен общий префикс, темно-фиолетовым первый отличный элемент, так как [math]4 \lt 6[/math] , то первая перестановка лексикографически меньше)
  • Сочетания (так как [math]4 \lt 6[/math] , то первое сочетание лексикографически меньше)
  • Разбиение на слагаемые (так как [math]4 \lt 9[/math] , то первое разбиение на слагаемые лексикографически меньше)
  • Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке ( [math]000[/math] , [math]001[/math] , [math]002[/math] , [math]003[/math] , [math]004[/math] , [math]005[/math] , [math]\dots[/math] , [math]999[/math] ).
  • Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, [math]AAA[/math] , [math]AAB[/math] , [math]AAC[/math] , [math]AAD[/math] , [math]\dots[/math] , [math]ZZZ[/math] .
  • Эти слова тоже записаны в лексикографическом порядке: [math]airport[/math] , [math]duck[/math] , [math]horse[/math] , [math]house[/math] , [math]sleep[/math] .

См. также

  • Генерация комбинаторных объектов в лексикографическом порядке
  • Получение предыдущего объекта
  • Получение следующего объекта

Источники информации

  • Wikipedia — Lexicographical order
  • Википедия — Лексикографический порядок
  • Дискретная математика и алгоритмы
  • Комбинаторика

Что такое лексикографическое сравнение и что оно собой представляет?

Это сравнение «как в словаре» или «как в телефонном справочнике» — по алфавиту. Если первые буквы совпали, сравниваются вторые, если вторые совпали — третьи, и так далее.

Отслеживать
ответ дан 7 фев 2016 в 12:19
22.3k 2 2 золотых знака 34 34 серебряных знака 53 53 бронзовых знака

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

Слово a предшествует слову b ( a

Если первые m символов слов совпадают, после чего слово a кончается, то оно также считается предшествующим b (т.е. отсутствующий символ меньше любого символа).

Таким образом, относительно лексикографического порядка для строк верны следующие равенства и неравенства:

"abc" == "abc" //true "123" == "123" //true "123" < "124" //true "0999999" < "123" //true "123" < "3" //true "12" < "123" //true "123" < "1234" //true 

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

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

a<b

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

Примеры

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

Wikimedia Foundation . 2010 .

  • Голод в СССР 1946—1947
  • Мокуа-Вел

Полезное

Смотреть что такое "Лексикографический порядок" в других словарях:

  • ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК — порядок на прямом произведении частично упорядоченных множеств Х a, где множество индексов L вполне упорядочена, определяемый следующим образом: если тогда и только тогда, когда либо для, всех либо существует такое что для всех Множество X,… … Математическая энциклопедия
  • Порядок на мономах — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Линейный порядок на пространстве одночленов … Википедия
  • Многокритериальная оптимизация — или программирование (англ. Multi objective optimization),[1][2] это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения. Задача многокритериальной оптимизации встречаются во… … Википедия
  • Правильная скобочная последовательность — (ПСП) частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой… … Википедия
  • Правильная скобочная структура — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия
  • Правильные скобочные последовательности — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия
  • УПОРЯДОЧЕННАЯ ПОЛУГРУППА — полугруппа, наделенная структурой (частичного, вообще говоря) порядка стабильного относительно полугрупповой операции, т. е. для любых элементов а, b, с из следует и Если отношение на У. н. Sесть линейный порядок, то S наз. линейно упорядоченной… … Математическая энциклопедия
  • ряд — ▲ последовательность ↑ дискретный ряд дискретная последовательность. хвост (# обязанностей). вереница (# дней). череда. чреда. гряда (# лет). цепь (# событий). цепочка. каскад. эстафета (# дней). очередность (# действий). очередь (# дел. чья #?… … Идеографический словарь русского языка
  • Строковый тип — В программировании, строковый тип (англ. string «нить, вереница») тип данных, значениями которого является произвольная последовательность (строка) символов алфавита. Каждая переменная такого типа (строковая переменная) может быть… … Википедия
  • ISO 8601 — ISO 8601 международный стандарт, выданный организацией ISO (International Organization for Standardization), который описывает формат даты и времени и даёт рекомендации для его использования в международном контексте. Название нормы … … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,

WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Поделиться ссылкой на выделенное

Прямая ссылка:

Нажмите правой клавишей мыши и выберите «Копировать ссылку»

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

Лексикографический порядок последовательностей это естественный способ упорядочивания последовательностей на основе сравнения индивидуальных символов.

Определение [ ]

Пусть дано конечное семейство множеств < A n >n = 1 N _^N> , и на каждом множестве A n задано отношение частичного порядка ⪯ n . Тогда на их декартовом произведении A 1 × ⋯ × A N можно определить частичный порядок ⪯ N следующим образом:

Замечание [ ]

Неформально говоря, лексикографический порядок задаётся следующей процедурой. Сравним первые символы в обоих словах. Если они равны, переходим ко вторым и так далее.

Примеры [ ]

  • последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999)
  • порядок Эта статья является заготовкой. Вы можете помочь проекту, добавив сюда новый материал.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *