Lexicographic order

From Wikipedia for FEVERv2
(Redirected from Lexicographical order)
Jump to navigation Jump to search

For similarly named ordering systems outside mathematics, see alphabetical order, natural sort order, lexicographic preferences, and collation. Lexicographic order_sentence_0

In mathematics, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set. Lexicographic order_sentence_1

There are several variants and generalizations of the lexicographical ordering. Lexicographic order_sentence_2

One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements. Lexicographic order_sentence_3

Another variant, widely used in combinatorics, orders subsets of a given finite set by assigning a total order to the finite set, and converting subsets into increasing sequences, to which the lexicographical order is applied. Lexicographic order_sentence_4

A generalization defines an order on a Cartesian product of partially ordered sets; this order is a total order if and only if all factors of the Cartesian product are totally ordered. Lexicographic order_sentence_5

Motivation and definition Lexicographic order_section_0

The words in a lexicon (the set of words used in some language) have a conventional ordering, used in dictionaries and encyclopedias, that depends on the underlying ordering of the alphabet of symbols used to build the words. Lexicographic order_sentence_6

The lexicographical order is one way of formalizing word order given the order of the underlying symbols. Lexicographic order_sentence_7

The formal notion starts with a finite set A, often called the alphabet, which is totally ordered. Lexicographic order_sentence_8

That is, for any two symbols a and b in A that are not the same symbol, either a < b or b < a. Lexicographic order_sentence_9

Lexicographic order_ordered_list_0

  1. Given two different words of the same length, say a = a1a2...ak and b = b1b2...bk, the order of the two words depends on the alphabetic order of the symbols in the first place i where the two words differ (counting from the beginning of the words): a < b if and only if ai < bi in the underlying order of the alphabet A.Lexicographic order_item_0_0
  2. If two words have different lengths, the usual lexicographical order pads the shorter one with "blanks" (a special symbol that is treated as smaller than every element of A) at the end until the words are the same length, and then the words are compared as in the previous case.Lexicographic order_item_0_1

However, in combinatorics, another convention is frequently used for the second case, whereby a shorter sequence is always smaller than a longer sequence. Lexicographic order_sentence_10

This variant of the lexicographical order is sometimes called shortlex order. Lexicographic order_sentence_11

In lexicographical order, the word "Thomas" appears before "Thompson" because they first differ at the fifth letter ('a' and 'p'), and letter 'a' comes before the letter 'p' in the alphabet. Lexicographic order_sentence_12

Because it is the first difference, in this case the 5th letter is the "most significant difference" for alphabetical ordering. Lexicographic order_sentence_13

An important property of the lexicographical order is that for each n, the set of words of length n is well-ordered by the lexicographical order (provided the alphabet is finite); that is, every decreasing sequence of words of length n is finite (or equivalently, every non-empty subset has a least element). Lexicographic order_sentence_14

It is not true that the set of all finite words is well-ordered; for example, the set { 1, 01, 001, 0001, ... } has no least element. Lexicographic order_sentence_15

Numeral systems and dates Lexicographic order_section_1

The lexicographical order is used not only in dictionaries, but also commonly for numbers and dates. Lexicographic order_sentence_16

One of the drawbacks of the Roman numeral system is that it is not always immediately obvious which of two numbers is the smaller. Lexicographic order_sentence_17

On the other hand, with the positional notation of the Hindu–Arabic numeral system, comparing numbers is easy, because the natural order on nonnegative integers is the same as the variant shortlex of the lexicographic order. Lexicographic order_sentence_18

In fact, with positional notation, a nonnegative integer is represented by a sequence of numerical digits, and an integer is larger than another one if either it has more digits (ignoring leading zeroes) or the number of digits is the same and the first (most significant) digit which differs is larger. Lexicographic order_sentence_19

For real numbers written in decimal notation, a slightly different variant of the lexicographical order is used: the parts on the left of the decimal point are compared as before; if they are equal, the parts at the right of the decimal point are compared with the lexicographical order. Lexicographic order_sentence_20

The padding 'blank' in this context is a trailing "0" digit. Lexicographic order_sentence_21

When negative numbers are also considered, one has to reverse the order for comparing negative numbers. Lexicographic order_sentence_22

This is not usually a problem for humans, but it may be for computers (testing the sign takes some time). Lexicographic order_sentence_23

This is one of the reasons for adopting two's complement representation for representing signed integers in computers. Lexicographic order_sentence_24

Another example of a non-dictionary use of lexicographical ordering appears in the ISO 8601 standard for dates, which expresses a date as YYYY-MM-DD. Lexicographic order_sentence_25

This formatting scheme has the advantage that the lexicographical order on sequences of characters that represent dates coincides with the chronological order: an earlier date is smaller in the lexicographical order than a later date. Lexicographic order_sentence_26

This date ordering makes computerized sorting of dates easier by avoiding the need for a separate sorting algorithm. Lexicographic order_sentence_27

Monoid of words Lexicographic order_section_2

With this terminology, the above definition of the lexicographical order becomes more concise: Given a partially or totally ordered set A, and two words a and b over A such that b is non-empty, then one has a < b under lexicographical order, if at least one of the following conditions is satisfied: Lexicographic order_sentence_28

Lexicographic order_unordered_list_1

  • a is a prefix of bLexicographic order_item_1_2
  • there exists words u, v, w (possibly empty) and elements x and y of A such thatLexicographic order_item_1_3

Lexicographic order_description_list_2

  • Lexicographic order_item_2_4
    • x < yLexicographic order_item_2_5
    • a = uxvLexicographic order_item_2_6
    • b = uywLexicographic order_item_2_7

If < is a total order on A, then so is the lexicographic order on the words of A. Lexicographic order_sentence_29

However, in general this is not a well-order, even if the alphabet A is well-ordered. Lexicographic order_sentence_30

For instance, if A = {a, b}, the language {ab | n ≥ 0, b > ε} has no least element in the lexicographical order: ... < aab < ab < b. Lexicographic order_sentence_31

Since many applications require well orders, a variant of the lexicographical orders is often used. Lexicographic order_sentence_32

This well-order, sometimes called shortlex or quasi-lexicographical order, consists in considering first the lengths of the words (if length(a) < length(b), then a < b), and, if the lengths are equal, using the lexicographical order. Lexicographic order_sentence_33

If the order on A is a well-order, the same is true for the shortlex order. Lexicographic order_sentence_34

Cartesian products Lexicographic order_section_3

The lexicographical order defines an order on a Cartesian product of ordered sets, which is a total order when all these sets are themselves totally ordered. Lexicographic order_sentence_35

An element of a Cartesian product E1× ... ×En is a sequence whose ith element belongs to Ei for every i. Lexicographic order_sentence_36

As evaluating the lexicographical order of sequences compares only elements which have the same rank in the sequences, the lexicographical order extends to Cartesian products of ordered sets. Lexicographic order_sentence_37

Specifically, given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as Lexicographic order_sentence_38

Lexicographic order_description_list_3

  • (a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).Lexicographic order_item_3_8

The result is a partial order. Lexicographic order_sentence_39

If A and B are each totally ordered, then the result is a total order as well. Lexicographic order_sentence_40

The lexicographical order of two totally ordered sets is thus a linear extension of their product order. Lexicographic order_sentence_41

One can define similarly the lexicographic order on the Cartesian product of an infinite family of ordered sets, if the family is indexed by the nonnegative integers, or more generally by a well-ordered set. Lexicographic order_sentence_42

This generalized lexicographical order is a total order if each factor set is totally ordered. Lexicographic order_sentence_43

Unlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order. Lexicographic order_sentence_44

For instance, the set of countably infinite binary sequences (by definition, the set of functions from non-negative integers to {0, 1}, also known as the Cantor space {0, 1}) is not well-ordered; the subset of sequences that have precisely one 1 (i.e. { 100000..., 010000..., 001000..., ... }) does not have a least element under the lexicographical order induced by 0 < 1, because 100000... > 010000... > 001000... > ... is an infinite descending chain. Lexicographic order_sentence_45

Similarly, the infinite lexicographic product is not Noetherian either because 011111... < 101111... < 110111 ... < ... is an infinite ascending chain. Lexicographic order_sentence_46

Functions over a well-ordered set Lexicographic order_section_4

The functions from a well-ordered set X to a totally ordered set Y may be identified with sequences indexed by X of elements of Y. Lexicographic order_sentence_47

They can thus be ordered by the lexicographical order, and for two such functions f and g, the lexicographical order is thus determined by their values for the smallest x such that f(x) ≠ g(x). Lexicographic order_sentence_48

If Y is also well-ordered and X is finite, then the resulting order is a well-order. Lexicographic order_sentence_49

As shown above, if X is infinite this is not the case. Lexicographic order_sentence_50

Finite subsets Lexicographic order_section_5

In combinatorics, one has often to enumerate, and therefore to order the finite subsets of a given set S. For this, one usually chooses an order on S. Then, sorting a subset of S is equivalent to convert it into an increasing sequence. Lexicographic order_sentence_51

The lexicographic order on the resulting sequences induces thus an order on the subsets, which is also called the lexicographical order. Lexicographic order_sentence_52

In this context, one generally prefer to sort first the subsets by cardinality, such as in the shortlex order. Lexicographic order_sentence_53

Therefore, in the following, we will consider only orders on subsets of fixed cardinal. Lexicographic order_sentence_54

For example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of S = {1, 2, 3, 4, 5, 6} is Lexicographic order_sentence_55

Lexicographic order_description_list_4

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

For ordering finite subsets of a given cardinality of the natural numbers, the colexicographical order (see below) is often more convenient, because all initial segments are finite, and thus the colexicographical order defines an order isomorphism between the natural numbers and the set of sets of n natural numbers. Lexicographic order_sentence_56

This is not the case for the lexicographical order, as, with the lexicographical order, we have, for example, 12n < 134 for every n > 2. Lexicographic order_sentence_57

Colexicographic order Lexicographic order_section_6

The colexicographic or colex order is a variant of the lexicographical order that is obtained by reading finite sequences from the right to the left instead of reading them from the left to the right. Lexicographic order_sentence_58

More precisely, whereas the lexicographical order between two sequences is defined by Lexicographic order_sentence_59

Lexicographic order_description_list_5

  • a1a2...ak < b1b2 ... bk if ai < bi for the first i where ai and bi differ,Lexicographic order_item_5_11

the colexicographical order is defined by Lexicographic order_sentence_60

Lexicographic order_description_list_6

  • a1a2...ak < b1b2...bk if ai < bi for the last i where ai and bi differLexicographic order_item_6_12

In general, the difference between the colexicographical order and the lexicographical order is not very significant. Lexicographic order_sentence_61

However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly. Lexicographic order_sentence_62

For example, for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by Lexicographic order_sentence_63

Lexicographic order_description_list_7

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

and the colexicographic order begins by Lexicographic order_sentence_64

Lexicographic order_description_list_8

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

The main property of the colexicographical order for increasing sequences of a given length is that every initial segment is finite. Lexicographic order_sentence_65

In other words, the colexicographical order for increasing sequences of a given length induces an order isomorphism with the natural numbers, and allows enumerating these sequences. Lexicographic order_sentence_66

This is frequently used in combinatorics, for example in the proof of the Kruskal-Katona theorem. Lexicographic order_sentence_67

Monomials Lexicographic order_section_7

One of these admissible orders is the lexicographical order. Lexicographic order_sentence_68

It is, historically, the first to have been used for defining Gröbner bases, and is sometimes called pure lexicographical order for distinguishing it from other orders that are also related to a lexicographical order. Lexicographic order_sentence_69

Another one consists in comparing first the total degrees, and then resolving the conflicts by using the lexicographical order. Lexicographic order_sentence_70

This order is not widely used, as either the lexicographical order or the degree reverse lexicographical order have generally better properties. Lexicographic order_sentence_71

The degree reverse lexicographical order consists also in comparing first the total degrees, and, in case of equality of the total degrees, using the reverse of the colexicographical order. Lexicographic order_sentence_72

That is, given two exponent vectors, one has Lexicographic order_sentence_73

if either Lexicographic order_sentence_74

or Lexicographic order_sentence_75

For this ordering, the monomials of degree one have the same order as the corresponding indeterminates (this would not be the case if the reverse lexicographical order would be used). Lexicographic order_sentence_76

For comparing monomials in two variables of the same total degree, this order is the same as the lexicographic order. Lexicographic order_sentence_77

This is not the case with more variables. Lexicographic order_sentence_78

For example, for exponent vectors of monomials of degree two in three variables, one has for the degree reverse lexicographic order: Lexicographic order_sentence_79

For the lexicographical order, the same exponent vectors are ordered as Lexicographic order_sentence_80

A useful property of the degree reverse lexicographical order is that a homogeneous polynomial is a multiple of the least indeterminate if and only if its leading monomial (its greater monomial) is a multiple of this least indeterminate. Lexicographic order_sentence_81

See also Lexicographic order_section_8

Lexicographic order_unordered_list_9


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Lexicographic order.