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

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

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

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

Примеры

Полезное

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

ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК — порядок на прямом произведении частично упорядоченных множеств Х a, где множество индексов L вполне упорядочена, определяемый следующим образом: если тогда и только тогда, когда либо для, всех либо существует такое что для всех Множество X,… … Математическая энциклопедия

Порядок на мономах — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Линейный порядок на пространстве одночленов … Википедия

Многокритериальная оптимизация — или программирование (англ. Multi objective optimization),[1][2] это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения. Задача многокритериальной оптимизации встречаются во… … Википедия

Правильная скобочная последовательность — (ПСП) частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой… … Википедия

Правильная скобочная структура — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия

Правильные скобочные последовательности — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия

УПОРЯДОЧЕННАЯ ПОЛУГРУППА — полугруппа, наделенная структурой (частичного, вообще говоря) порядка стабильного относительно полугрупповой операции, т. е. для любых элементов а, b, с из следует и Если отношение на У. н. Sесть линейный порядок, то S наз. линейно упорядоченной… … Математическая энциклопедия

ряд — ▲ последовательность ↑ дискретный ряд дискретная последовательность. хвост (# обязанностей). вереница (# дней). череда. чреда. гряда (# лет). цепь (# событий). цепочка. каскад. эстафета (# дней). очередность (# действий). очередь (# дел. чья #?… … Идеографический словарь русского языка

Строковый тип — В программировании, строковый тип (англ. string «нить, вереница») тип данных, значениями которого является произвольная последовательность (строка) символов алфавита. Каждая переменная такого типа (строковая переменная) может быть… … Википедия

ISO 8601 — ISO 8601 международный стандарт, выданный организацией ISO (International Organization for Standardization), который описывает формат даты и времени и даёт рекомендации для его использования в международном контексте. Название нормы … … Википедия

Источник

Алгоритм: Как найти следующую лексикографическую перестановку

Если кратко описать, что такое лексикографический порядок — это сортировка в алфавитном порядке. Т.е. последовательность символов — AAA → AAB → AAC → AAD → ……… → WWW — является отсортированной в алфавитном (или в нашем случае лексикографическом) порядке.

Представьте, что у Вас есть конечная последовательность символов, например 0, 1, 2, 5, 3, 3, 0 и Вам необходимо найти все возможные перестановки этих символов. Наиболее интуитивным, но и наибольшим по сложности, является рекурсивный алгоритм, когда мы выбираем первый символ из последовательности, далее рекурсивно выбираем второй, третий итд, до тех пор, пока все символы из последовательности не будет выбраны. Понятно, что сложность такого алгоритма — O(n!).

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

Точно также, как при расчете следующего целочисленного значения, мы должны стараться увеличить правую часть последовательности и оставить левую часть неизменной.

В качестве примера возьмем вышеприведенную последовательность — (0, 1, 2, 5, 3, 3, 0). Чтобы получить последовательность выше оригинальной, достаточно переставить первый и второй элементе местами, но в этом нет необходимости, так как можно переставить второй и и третий и получив более близкую по возрастанию последовательность. что приведет нас к следующей более близкой перестановки итд.

Наиболее оптимальным алгоритмом в этом случае будет следующий:

Это значение и будет следующей лексикографической перестановкой.

Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))

Для простоты весь код будет написан на Go и думаю никому не составить труда перевести его на любой другой язык программирования.

Большое спасибо PYXRU и 646f67, что ткнули меня носом в возможную оптимизацию алгоритма — произвести расчет перестановки за линейную сложность просто сделав reverse суффикса.

Источник

Математика

In the coming weeks, this wiki’s URL will be migrated to the primary fandom.com domain. Read more here

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

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

Определение

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

.

Замечание

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

Примеры

Эта статья содержит материал из статьи Лексикографический порядок русской Википедии.

Источник

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

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

Обобщение определяет порядок на декартово произведение из частично упорядоченных множеств ; этот порядок является полным, если и только если все факторы декартова произведения полностью упорядочены.

СОДЕРЖАНИЕ

Мотивация и определение [ править ]

В лексикографическом порядке слово «Томас» появляется перед «Томпсон», потому что они сначала различаются по пятой букве («а» и «р»), а буква «а» стоит перед буквой «р» в алфавите. Поскольку это первое различие, в данном случае пятая буква является «наиболее существенным различием» для алфавитного порядка.

Системы счисления и даты [ править ]

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

Когда также рассматриваются отрицательные числа, необходимо изменить порядок сравнения отрицательных чисел. Обычно это не проблема для людей, но может быть и для компьютеров (проверка знака занимает некоторое время). Это одна из причин для принятия представления с дополнением до двух для представления целых чисел со знаком в компьютерах.

Другой пример использования лексикографического упорядочения вне словаря появляется в стандарте ISO 8601 для дат, который выражает дату как ГГГГ-ММ-ДД. Эта схема форматирования имеет то преимущество, что лексикографический порядок последовательностей символов, представляющих даты, совпадает с хронологическим порядком : более ранняя дата в лексикографическом порядке меньше, чем более поздняя дата. Такое упорядочение дат упрощает компьютеризированную сортировку дат, устраняя необходимость в отдельном алгоритме сортировки.

Моноид слов [ править ]

С помощью этой терминологии приведенное выше определение лексикографического порядка становится более кратким: если дано частично или полностью упорядоченное множество A и два слова a и b над A, такие что b непусто, то одно имеет a в лексикографическом порядке, если выполняется хотя бы одно из следующих условий:

Декартовы произведения [ править ]

В частности, для двух частично упорядоченных наборов A и B лексикографический порядок декартового произведения A × B определяется как

Аналогичным образом можно определить лексикографический порядок декартова произведения бесконечного семейства упорядоченных множеств, если семейство проиндексировано неотрицательными целыми числами или, в более общем смысле, хорошо упорядоченным множеством. Этот обобщенный лексикографический порядок является полным, если каждый набор факторов полностью упорядочен.

Функции над упорядоченным набором [ править ]

Если Y также хорошо упорядочен, а X конечно, то полученный порядок является хорошим порядком. Как показано выше, если X бесконечно, это не так.

Конечные подмножества [ править ]

Например, используя естественный порядок целых чисел, лексикографический порядок на подмножествах трех элементов S = <1, 2, 3, 4, 5, 6>равен

Колексикографический порядок [ править ]

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

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

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

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

Мономы [ править ]

Одним из таких допустимых порядков является лексикографический порядок. Исторически он был первым, который использовался для определения основ Гребнера, и иногда его называют чистым лексикографическим порядком, чтобы отличить его от других порядков, которые также связаны с лексикографическим порядком.

Степень обратного Лексикографическое порядок заключается также в сравнении первых полных градусов, а в случае равенства полных степеней, используя обратную сторону colexicographical порядка. То есть, учитывая два вектора экспоненты, один имеет

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

Для лексикографического порядка те же векторы экспоненты упорядочены как

Полезное свойство обратного лексикографического порядка степени состоит в том, что однородный многочлен кратен наименее неопределенному тогда и только тогда, когда его старший моном (его старший моном) кратен этому наименее неопределенному.

Источник

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

Обобщение определяет порядок на декартово произведение из частично упорядоченных множеств ; этот порядок является полным, если и только если все факторы декартова произведения полностью упорядочены.

СОДЕРЖАНИЕ

Мотивация и определение

В лексикографическом порядке слово «Томас» появляется перед «Томпсон», потому что они сначала различаются по пятой букве («а» и «р»), а буква «а» стоит перед буквой «р» в алфавите. Поскольку это первое различие, в данном случае пятая буква является «наиболее существенным различием» для алфавитного порядка.

Системы счисления и даты

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

Когда также рассматриваются отрицательные числа, необходимо изменить порядок сравнения отрицательных чисел. Обычно это не проблема для людей, но может быть и для компьютеров (проверка знака занимает некоторое время). Это одна из причин для принятия представления с дополнением до двух для представления целых чисел со знаком в компьютерах.

Другой пример использования лексикографического упорядочения вне словаря появляется в стандарте ISO 8601 для дат, который выражает дату как ГГГГ-ММ-ДД. Эта схема форматирования имеет то преимущество, что лексикографический порядок последовательностей символов, представляющих даты, совпадает с хронологическим порядком : более ранняя дата CE в лексикографическом порядке меньше, чем более поздняя дата вплоть до 9999 года. Такое упорядочение дат обеспечивает компьютеризированную сортировку дат. проще, поскольку нет необходимости в отдельном алгоритме сортировки.

Моноид слов

С помощью этой терминологии приведенное выше определение лексикографического порядка становится более кратким: если дано частично или полностью упорядоченное множество A и два слова a и b над A, такие, что b непусто, то одно имеет a в лексикографическом порядке, если выполняется хотя бы одно из следующих условий:

Декартовы произведения

Аналогичным образом можно определить лексикографический порядок декартова произведения бесконечного семейства упорядоченных множеств, если семейство индексировано неотрицательными целыми числами или, в более общем смысле, хорошо упорядоченным множеством. Этот обобщенный лексикографический порядок является полным, если каждый набор факторов полностью упорядочен.

Функции над упорядоченным набором

Конечные подмножества

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

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

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

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

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

Мономы

Одним из таких допустимых порядков является лексикографический порядок. Исторически он был первым, который использовался для определения основ Гребнера, и иногда его называют чистым лексикографическим порядком, чтобы отличить его от других порядков, которые также связаны с лексикографическим порядком.

Степень обратного Лексикографическое порядок заключается также в сравнении первых полных градусов, а в случае равенства полных степеней, используя обратную сторону colexicographical порядка. То есть, учитывая два вектора экспоненты, один имеет

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

Для лексикографического порядка те же векторы экспоненты упорядочены как

Полезное свойство обратного лексикографического порядка степени состоит в том, что однородный многочлен кратен наименее неопределенному тогда и только тогда, когда его старший моном (его старший моном) кратен этому наименее неопределенному.

Источник