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

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

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

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

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

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

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

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

1. Прежде всего Вы должны найти наибольший не-увеличивающийся суффикс. В вышеприведенном примере это будет — (5, 3, 3, 0). Если Вы попробуете сделать любую перестановку в данной последовательности, то она не будет выше оригинальной.
   Стоит сказать, что найти данную последовательность вы можете за O(n) времени, просматривая последовательность слева направо.
2. Следующий элемент от суффикса является точкой поворота. В нашем случае — это 2. Точка поворота будет всегда меньше первого элемента суффикса. Это значит, что в суффиксе обязательно будет элемент превышающий точку поворота и если мы поменяет точку поворота на наименьший элемента из суффикса, превышающий опорный элемент точки поворота — мы получим последовательность превышающую оригинальную — в нашем случает это будет — (0, 1, 3, 5, 3, 2, 0).
   Т.е. результатом этой операции будет минимально возможный по возрастанию префикс.
3. И на последнем шаге мы должны отсортировать суффикс в порядке возрастания. Т.е. мы получим минимально возможный суффикс. В нашем примере это будет (0, 2, 3, 5) и вся последовательность будет выглядеть как (0, 1, 3, 0, 2, 3, 5).

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

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

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

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

Заслуживающим отдельного упоминания является лексикографический порядок. Лексикографический порядок — это порядок, в котором выстроены слова, например, в русско-английских словарях. Лексикографический порядок может быть введен на множестве слов над любым множеством, на котором уже введен линейный порядок.

Пусть на множестве X введен строгий линейный порядок ≺. Введем

отношение ≺_lex на множестве X ∗ = <(x₁, x₂, . x_k) | k ∈ N, x_i ∈ X> всех

x_k = (x₁, . x_k) ∈ X ∗ , y_l = (y₁, . y_l) ∈

x_k /= y_l и k ≤ l.

x k ≺ lex y l

Будем говорить, что

, если 1) существует такой индекс t,

1 ≤ t ≤ k, что x_i = y_i, i = 1, t − 1 и x_t ≺ y_t, или 2) k < l и x_i = y_i, i = 1, k.

y l ≺ lex x k

В противном случае .

Замечание 1.4.3 . На множестве слов одинаковой длины определение лексикографического порядка упростилось бы и приняло бы вид:

x k ≺ lex y k

= y , i = 1, t − 1, x

Пример 1.4.9 . Выпишем все возможные перестановки чисел <1,2, 3, 4> выстроенные в лексикографическом порядке:

Заметим, что здесь мы привели только перестановки — последовательности из различных символов. Если мы захотим выписать все слова в данном алфавите, их окажется гораздо больше.

Подробнее о перестановках смотри раздел 1.6.

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

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

y l ≺ alex

Будем говорить, что

, если 1) существует такой индекс t,

y l ≺ alex x k

Замечание 1.4.4 . На множестве слов одинаковой длины определение приняло бы следующий вид:

x k ≺ alex y k

= y , i = t + 1, k, y

Пример 1.4.10 . Приведем все возможные перестановки чисел <1,2, 3, 4> выстроенные в антилексикографическом порядке:

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

• [math] n \lt m [/math] и при этом [math] a_i = b_i [/math] для всех [math]i \in [1 .. n] [/math] ,
• [math] \exists k\leqslant \min(n, m): a_k \lt b_k [/math] и при этом [math] \forall j : j \lt k

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

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

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

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

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

Примеры

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

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

• Математические отношения
• Лексикография
• Концепции языков программирования

Wikimedia Foundation . 2010 .

Полезное

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

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

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

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

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

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

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

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

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

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

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