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

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

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

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

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

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

Содержание

  • 1 Мотивация и определение
  • 2 Системы счисления и даты
  • 3 Моноид слов
  • 4 Декартовы произведения
  • 5 Функции над упорядоченным множеством
  • 6 Конечные подмножества
  • 7 Групповые порядки Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n}
  • 8 Колексикографический порядок
  • 9 Мономы
  • 10 См. Также
  • 11 Ссылки
  • 12 Внешние ссылки

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

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

Формальное понятие начинается с конечного множества A, часто называемого алфавитом, которое является полностью упорядоченным. То есть, для любых двух символов a и b в A, которые не являются одним и тем же символом, либо a < b or b < a.

Слова A являются конечными последовательностями символов из A, включая слова длины 1, содержащие один символ, слова длины 2 с двумя символами и так далее, даже включая пустую последовательность ε {\ displaystyle \ varepsilon}\ varepsilon без каких-либо символов. Лексикографический порядок на множестве всех этих конечных слов упорядочивает слова следующим образом:

  1. Для двух разных слов одинаковой длины, скажем, a = a 1a2... a k и b = b 1b2... b k, порядок двух слов зависит от алфавитного порядка символов в первом месте i, где два слова различаются (считая с начала слов): a < b if and only if ai< biв нижележащем порядке алфавита A.
  2. Если два слова имеют разную длину, обычный лексикографический порядок дополняет более короткое слово «пробелами» (специальный символ, который считается меньшим, чем каждый элемент из A) до тех пор, пока слова не станут одинаковой длины, а затем слова сравниваются, как в предыдущем случае.

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

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

Важным свойством лексикографического порядка является то, что для каждого n набор слов длины n хорошо упорядочен в соответствии с лексикографическим порядком (при условии, что алфавит конечен); то есть каждая убывающая последовательность слов длины n конечна (или, что эквивалентно, каждое непустое подмножество имеет наименьший элемент). Неправда, что множество всех конечных слов хорошо упорядочено; например, набор {1, 01, 001, 0001,...} не имеет наименьшего элемента.

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

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

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

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

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

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

Моноид слов

Моноид слов над алфавитом A - это свободный моноид над A. То есть элементы моноида - это конечные последовательности (слова) элементов A (включая пустую последовательность длины 0), а операция (умножение) - это конкатенация слов. Слово u является префиксом (или «усечением») другого слова v, если существует такое слово w, что v = uw. По этому определению пустое слово (ε {\ displaystyle \ varepsilon}\ varepsilon ) является префиксом каждого слова, а каждое слово является префиксом самого себя (с w = ε {\ displaystyle = \ varepsilon}{\ displaystyle = \ varepsilon} ); Необходимо соблюдать осторожность, чтобы исключить эти случаи.

С помощью этой терминологии приведенное выше определение лексикографического порядка становится более кратким: для частично или полностью упорядоченного множества A и двух слов a и b над A такое, что b не пусто, то есть a < b under lexicographical order, if at least one of the following conditions is satisfied:

  • a является префиксом b
  • существуют слова u, v, w (возможно, пустые) и элементы x и y из A такие, что
x < y
a = uxv
b = uyw

Обратите внимание, что из-за условия префикса в этом определении ε < b ∀ b ≠ ε {\displaystyle \varepsilon {\ displaystyle \ varepsilon <b \, \, \ forall b \ neq \ varepsilon} , где ε {\ displaystyle \ varepsilon}\ varepsilon - пустое слово.

Если < is a total order on A, then so is the lexicographic order on the words of A. However, in general this is not a правильный порядок, даже если алфавит A хорошо упорядочен. Например, если A = {a, b}, язык {ab | n ≥ 0, b>ε} не имеет наименьшего элемента в лексикографическом порядке:... < aab < ab < b.

Поскольку многие приложения требуют хороших порядков, часто используется вариант лексикографического порядка. Этот правильный порядок, иногда называемый shortlex или квазилексикографическим порядком, заключается в рассмотрении сначала длины слов (если длина (a) < length(b), then a < b), and, if the lengths are equal, using the lexicographical order. If the order on A is a well-order, the same is true for the shortlex order.

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

Лексикографический порядок определяет порядок на декартовом произведении упорядоченных наборов, который является общим порядком, когда все эти наборы сами полностью упорядочены. Элемент декартова произведения E 1 ×... × E n - последовательность, i-й элемент которой принадлежит E i для каждого i. Поскольку при оценке лексикографического порядка последовательностей сравниваются только элементы, которые имеют одинаковый ранг в последовательностях, лексикографический порядок расширяется в декартово произведение упорядоченных множеств.

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

(a, b) ≤ (a ′, b ′) тогда и только тогда, когда a < a′ or (a = a′ and b ≤ b′).

Результатом является частичный порядок. Если каждый из A и B полностью упорядочен, то результат также является полным порядком. лексикограф Таким образом, логический порядок двух полностью упорядоченных множеств является линейным расширением их порядка произведения.

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

В отличие от конечного случая, бесконечный продукт хороших порядков не обязательно хорошо упорядочен лексикографическим порядком. Например, набор счетно бесконечных двоичных последовательностей (по определению, набор функций от неотрицательных целых чисел до {0, 1}, также известный как пространство Кантора {0, 1}) неупорядочен; подмножество последовательностей, которые имеют ровно одну единицу (т. е. {100000..., 010000..., 001000...,...}), не имеет минимального элемента в лексикографическом порядке, индуцированном 0 < 1, because 100000...>010000...>001000...>... - это бесконечная убывающая цепочка. Точно так же бесконечный лексикографический продукт не является нётерским, потому что 011111... < 101111... < 110111... <... is an infinite ascending chain.

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

Функции из хорошо упорядоченного набор X в полностью упорядоченный набор Y может быть идентифицирован последовательностями, индексированными X элементов Y. Таким образом, они могут быть упорядочены в лексикографическом порядке, и для двух таких функций f и g лексикографический порядок таким образом определяется их значениями для наименьшего x, такого что f (x) ≠ g (x).

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

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

Порядок 3- подмножеств из {1,..., 6}, представленных в виде наборов красных квадратов, возрастающих последовательностей (синим цветом) или их индикаторные функции, преобразованные в десятичную форму (серого цвета). Серые числа также являются рангом подмножеств во всех подмножествах {1,..., 6}, пронумерованных в колексикографическом порядке, начиная с 0. Лексикографический (lex) и колексикографический (colex) порядки находятся наверху и соответствующие обратные порядки (обороты) внизу. Переход от порядка к его обратному порядку осуществляется либо путем чтения снизу вверх, а не снизу вверх, либо путем обмена красным и белым цветами.

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

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

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

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <
234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456.

Для упорядочивания конечных подмножеств заданной мощности натуральных чисел колексикографический порядок (см. Ниже) часто более удобен, поскольку все начальные сегменты конечны, и, следовательно, колексикографический порядок определяет изоморфизм порядка между натуральными числами и множеством наборов из n натуральных чисел. Это не относится к лексикографическому порядку, так как с лексикографическим порядком мы имеем, например, 12n < 134 for every n>2.

Групповые заказы Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n}

Пусть Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} - это свободная абелева группа ранга n, элементы которой представляют собой последовательности из n целых чисел, а операция - это сложение. A групповой порядок на Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} - это общий порядок, который совместим с сложением, то есть

a < b ⟺ a + c < b + c. {\displaystyle a{\ displayst yle a <b \ quad \ Longleftrightarrow \ quad a + c <b + c.}

Лексикографический порядок - это групповой порядок на Z n. {\ displaystyle \ mathbb {Z} ^ {n}.}{\ displaystyle \ mathbb {Z} ^ {n}.}

Лексикографическое упорядочение также может использоваться для характеристики всех групповых порядков на Z n. {\ displaystyle \ mathbb {Z} ^ {n}.}{\ displaystyle \ mathbb {Z} ^ {n}.} Фактически, n линейные формы с действительными коэффициентами, определяют карту из Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} в R n, {\ displaystyle \ mathbb {R} ^ {n},}{\ displaystyle \ mathbb {R} ^ {n},} , что является инъективным если формы линейно независимы (он также может быть инъективным, если формы зависимы, см. ниже). Лексикографический порядок на изображении этой карты индуцирует групповой порядок на Z n. {\ displaystyle \ mathbb {Z} ^ {n}.}{\ displaystyle \ mathbb {Z} ^ {n}.} Теорема Роббиано гласит, что таким способом можно получить любой групповой порядок.

Точнее, при групповом порядке на Z n, {\ displaystyle \ mathbb {Z} ^ {n},}{\ displaystyle \ mathbb {Z} ^ {n},} существует целое число s ≤ n и s линейное формы с действительными коэффициентами, так что индуцированная карта φ {\ displaystyle \ varphi}\ varphi из Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} в R s {\ displaystyle \ mathbb {R} ^ {s}}{\ displaystyle \ mathbb {R} ^ {s}} имеет следующие свойства;

  • φ {\ displaystyle \ varphi}\ varphi инъективно;
  • результирующий изоморфизм из Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} к изображению φ {\ displaystyle \ varphi}\ varphi является изоморфизмом порядка, когда изображение снабжено лексикографическим порядком на R s. {\ displaystyle \ mathbb {R} ^ {s}.}{\ displaystyle \ mathbb {R} ^ {s }.}

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

Порядок 24 перестановок {1,..., 5}, которые являются 5-циклами (в синий). векторы инверсии (красным цветом) перестановок в порядке колекса находятся в порядке ревколекса, и наоборот.

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

a1a2... a k< b1b2... b k, если a i< biдля первого i, где a i и b i отличаются,

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

a1a2... a k< b1b2... b k, если a i< biдля last i, где a i и b i различаются

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

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

12 < 13 < 14 < 15 <... < 23 < 24 < 25 <... < 34 < 35 <... < 45 <...,

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

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 <....

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

Мономы

При рассмотрении полиномов порядок в общем случае члены не имеют значения, поскольку сложение коммутативно. Однако некоторые алгоритмы , такие как полиномиальное деление в столбик, требуют, чтобы термины располагались в определенном порядке. Многие из основных алгоритмов для многомерных многочленов связаны с базисами Грёбнера, концепцией, которая требует выбора мономиального порядка, то есть полного порядка, который совместим со структурой моноида мономов . Здесь «совместимый» означает, что a < b ⟹ a c < b c {\displaystyle a{\ displaystyle a <b \ implies ac <bc} , если операция моноида обозначена мультипликативно. Эта совместимость означает, что произведение многочлена на одночлен не меняет порядок членов. Для базисов Грёбнера должно выполняться дополнительное условие, а именно, что каждый непостоянный моном больше, чем моном 1. Однако это условие не требуется для других связанных алгоритмов, таких как алгоритмы для вычисления касательного конуса .

Поскольку базисы Грёбнера определены для многочленов от фиксированного числа переменных, мономы обычно идентифицируют (например, x 1 x 2 3 x 4 x 5 2 {\ displaystyle x_ {1} x_ {2} ^ {3} x_ {4} x_ {5} ^ {2}}x_ {1} x_ {2} ^ {3} x_ {4} x_ {5} ^ {2} ) с их векторами экспоненты (здесь [1, 3, 0, 1, 2]). Если n - количество переменных, каждый мономиальный порядок, таким образом, является ограничением до N n {\ displaystyle \ mathbb {N} ^ {n}}{\ displaystyle \ mathbb {N} ^ {n}} мономиального порядка Z n. {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} (см. выше § Групповые порядки Z n {\ displaystyle \ mathbb {Z} ^ {n}}{\ mathbb Z} ^ {n} , для классификации).

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

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

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

[a 1,…, an] < [ b 1, …, b n ] {\displaystyle [a_{1},\ldots,a_{n}]<[b_{1},\ldots,b_{n}]}{\ displaystyle [a_ {1}, \ ldots, a_ {n}] <[b_ {1}, \ ldots, b_ {n}]}

, если либо

a 1 + ⋯ + an < b 1 + ⋯ + b n, {\displaystyle a_{1}+\cdots +a_{n}{\ displaystyle a_ {1 } + \ cdots + a_ {n} <b_ {1} + \ cdots + b_ {n},}

, либо

a 1 + ⋯ + an = b 1 + ⋯ + bn и ai>bi для наибольшего i, для которого ai ≠ bi. {\ displaystyle a_ {1} + \ cdots + a_ {n} = b_ {1} + \ cdots + b_ {n} \ quad {\ text {and}} \ quad a_ {i}>b_ {i} {\ text {для наибольшего}} i {\ text {для которого}} a_ {i} \ neq b_ {i}.}{\displaystyle a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{and}}\quad a_{i}>b_ {i} {\ text {для наибольшего}} i {\ текст {для которого}} a_ {i} \ neq b_ {i}.}

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

[0, 0, 2] < [ 0, 1, 1 ] < [ 1, 0, 1 ] < [ 0, 2, 0 ] < [ 1, 1, 0 ] < [ 2, 0, 0 ] {\displaystyle [0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]}{\ displaystyle [0,0,2] <[0,1,1] <[1,0,1] <[0,2,0] <[1,1,0] <[ 2,0,0]}

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

[0, 0, 2] < [ 0, 1, 1 ] < [ 0, 2, 0 ] < [ 1, 0, 1 ] < [ 1, 1, 0 ] < [ 2, 0, 0 ]. {\displaystyle [0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].}{\ displaystyle [0,0,2 ] <[0,1,1] <[0,2,0] <[1,0,1] <[1,1,0] <[2,0,0].}

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

См. Также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-05-27 07:36:53
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте