Lexicographic order
This article needs additional citations for verification. (January 2022) |
In
There are several variants and generalizations of the lexicographical ordering. One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.
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.
A generalization defines an order on an n-ary 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.
Definition
The words in a
The formal notion starts with a
The words of A are the finite sequences of symbols from A, including words of length 1 containing a single symbol, words of length 2 with 2 symbols, and so on, even including the empty sequence with no symbols at all. The lexicographical order on the set of all these finite words orders the words as follows:
- 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.
- 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.
However, in combinatorics, another convention is frequently used for the second case, whereby a shorter sequence is always smaller than a longer sequence. This variant of the lexicographical order is sometimes called shortlex order.
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. Because it is the first difference, in this case the 5th letter is the "most significant difference" for alphabetical ordering.
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).[1][2] It is not true that the set of all finite words is well-ordered; for example, the infinite set of words {b, ab, aab, aaab, ... } has no lexicographically earliest element.
Numeral systems and dates
The lexicographical order is used not only in dictionaries, but also commonly for numbers and dates.
One of the drawbacks of the
For
When negative numbers are also considered, one has to reverse the order for comparing negative numbers. This is not usually a problem for humans, but it may be for
Another example of a non-dictionary use of lexicographical ordering appears in the
Monoid of words
The monoid of words over an alphabet A is the
With this terminology, the above definition of the lexicographical order becomes more concise: Given a
- a is a prefix of b
- there exists words u, v, w (possibly empty) and elements x and y of A such that
- x < y
- a = uxv
- b = uyw
Notice that, due to the prefix condition in this definition, where is the empty word.
If is a total order on then so is the lexicographic order on the words of However, in general this is not a well-order, even if the alphabet is well-ordered. For instance, if A = {a, b}, the language {anb | n ≥ 0, b > ε} has no least element in the lexicographical order: ... < aab < ab < b.
Since many applications require well orders, a variant of the lexicographical orders is often used. This well-order, sometimes called
Cartesian products
The lexicographical order defines an order on an n-ary Cartesian product of ordered sets, which is a total order when all these sets are themselves totally ordered. An element of a Cartesian product is a sequence whose th element belongs to for every 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.
Specifically, given two partially ordered sets and the lexicographical order on the Cartesian product is defined as
The result is a partial order. If and are each totally ordered, then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a linear extension of their product order.
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 natural numbers, or more generally by a well-ordered set. This generalized lexicographical order is a total order if each factor set is totally ordered.
Unlike the finite case, an infinite product of well-orders is not necessarily well-ordered by the lexicographical order. For instance, the set of
Functions over a well-ordered set
The functions from a
If is also well-ordered and is finite, then the resulting order is a well-order. As shown above, if is infinite this is not the case.
Finite subsets
In
In this context, one generally prefer to sort first the subsets by cardinality, such as in the shortlex order. Therefore, in the following, we will consider only orders on subsets of fixed cardinal.
For example, using the natural order of the integers, the lexicographical ordering on the subsets of three elements of is
- 123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <
- 234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456.
For ordering finite subsets of a given cardinality of the
Group orders of Zn
Let be the
The lexicographical ordering is a group order on
The lexicographical ordering may also be used to characterize all group orders on [4][5] In fact, linear forms with real coefficients, define a map from into which is injective if the forms are
More precisely, given a group order on there exist an integer and linear forms with real coefficients, such that the induced map from into has the following properties;
- is injective;
- the resulting isomorphism from to the image of is an order isomorphism when the image is equipped with the lexicographical order on
Colexicographic order
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. More precisely, whereas the lexicographical order between two sequences is defined by
- a1a2...ak <lex b1b2 ... bk if ai < bi for the first i where ai and bi differ,
the colexicographical order is defined by
- a1a2...ak <colex b1b2...bk if ai < bi for the last i where ai and bi differ
In general, the difference between the colexicographical order and the lexicographical order is not very significant. However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly.
For example, for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by
- 12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...,
and the colexicographic order begins by
- 12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ....
The main property of the colexicographical order for increasing sequences of a given length is that every
Monomials
When considering
As Gröbner bases are defined for polynomials in a fixed number of variables, it is common to identify monomials (for example ) with their exponent vectors (here [1, 3, 0, 1, 2]). If n is the number of variables, every monomial order is thus the restriction to of a monomial order of (see above § Group orders of for a classification).
One of these admissible orders is the lexicographical order. 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.
Another one consists in comparing first the
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. That is, given two exponent vectors, one has
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). For comparing monomials in two variables of the same total degree, this order is the same as the lexicographic order. This is not the case with more variables. For example, for exponent vectors of monomials of degree two in three variables, one has for the degree reverse lexicographic order:
For the lexicographical order, the same exponent vectors are ordered as
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.
See also
- Collation
- Kleene–Brouwer order
- Lexicographic preferences - an application of lexicographic order in economics.
- Lexicographic optimization - an algorithmic problem of finding a lexicographically-maximal element.
- Lexicographic order topology on the unit square
- Lexicographic ordering in tensor abstract index notation
- Lexicographically minimal string rotation
- Leximin order
- Long line (topology)
- Lyndon word
- Star product, a different way of combining partial orders
- Shortlex order
- Orders on the Cartesian product of totally ordered sets
References
- ^ ISBN 978-0-387-24222-4.
- ^ ISBN 978-0-521-77920-3.
- Zbl 0922.68073.
- ^ Robbiano, L. (1985). Term orderings on the polynomial ring. In European Conference on Computer Algebra (pp. 513-517). Springer Berlin Heidelberg.
- S2CID 10226875.
External links
- Learning materials related to Lexicographic and colexicographic order at Wikiversity