Lexicographical order

From Wikipedia, the free encyclopedia

In mathematics, the lexicographic or lexicographical order, (a.k.a. dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the cartesian product of two ordered sets. Given A and B, two ordered sets, the lexicographical order in the cartesian product A × B is defined as

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

The name comes from its generalizing the order given to words in a dictionary: a sequence of letters (i.e. a word)

a₁a₂ ... a_k

appears in a dictionary before a sequence

b₁b₂ ... b_k

if and only if the first a_i which is different from b_i comes before b_i in the alphabet. That assumes both have the same length; what is usually done is to pad out the shorter word for symbols for 'blanks', and to consider that a blank is a new minimum ('bottom') element.

For the purpose of dictionaries, etc., one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases. See alphabetical order.

An important property of the lexicographical order is that it preserves well-orders, that is, if A and B are well-ordered sets, then the product set A × B with the lexicographical order is also well-ordered.

An important exploitation of lexicographical ordering is expressed in the ISO 8601 date formatting scheme, which expresses a date as YYYY-MM-DD. This date ordering lends itself to straightforward computerized sorting of dates such that the sorting algorithm does not need to treat the numeric parts of the date string any differently from a string of non-numeric characters, and the dates will be sorted into chronological order. Note, however, that for this to work, there must always be four digits for the year, two for the month, and two for the day, so for example single-digit days must be padded with a zero yielding '01', '02', ... , '09'.

1 Case of multiple products
2 Ordering of strings
3 Monomials
4 Variations
- 4.1 Reverse lexicographic order
5 See also

[edit] Case of multiple products

Suppose

$\{ A_1, A_2, \dots, A_n \}$

is a collection of sets, with respective to total orderings

$\{ <_1, <_2, \cdots, <_n \}$

The dictionary ordering

$\ \ <^d$

$A_1 \times A_2 \times \cdots \times A_n$

is then

$(a_1, a_2, \dots, a_n) <^d (b_1,b_2, \dots, b_n) \iff (\exists\ m > 0) \ (\forall\ i < m) (a_i = b_i) \land (a_m <_m b_m)$

That is, if one of the terms

$\ \ a_m <_m b_m$

and all the preceding terms are equal.

Informally,

$\ \ a_1$

represents the first letter,

$\ \ a_2$

the second and so on when looking up a word in a dictionary, hence the name.

This could be more elegantly stated by recursively defining the ordering of any set

$\ \ C= A_j \times A_{j+1} \times \cdots \times A_k$

represented by

$\ \ <^d (C)$

This will satisfy

$a <^d (A_i) a' \iff (a <_i a')$

$(a,b) <^d (A_i \times B) (a',b') \iff a <^d (A) a' \lor ( a=a' \ \land \ b <^d (B) b')$

where $B = A_{i+1} \times A_{i+2} \times \cdots \times A_n.$

To put it even more simply, compare the first terms. If they are equal, compare the second terms — and so on. The relationship between the first corresponding terms that are not equal determines the relationship between the entire elements.

[edit] Ordering of strings

If $Σ$ is a finite and totally ordered alphabet, the above considerations allow to define naturally a lexicographical order $< d$ over the free monoid $Σ *$ (i.e., the set of all words over $Σ$ ), as follows:

u < d v

$u$ is a prefix of $v$ , or
$u = w a u'$ and $v = w b v'$ , where $w$ is the longest common prefix of $u$ and $v$ , $a$ and $b$ are letters of $Σ$ such that $a < b$ , and $u', v'$ are words.

However, in general this is not a well-order; for instance, if $Σ = {a, b}$ , the language $\{a^nb\mid n\geq 0\}$ has no least element. A well-order for strings, based on the lexicographical order, is the shortlex order.

[edit] Monomials

In algebra it is traditional to order terms in a polynomial, by ordering the monomials in the indeterminates. This is fundamental, in order to have a normal form. Such matters are typically left implicit in discussion between humans, but must of course be dealt with exactly in computer algebra. In practice one has an alphabet of indeterminates X, Y, ... and orders all monomials formed from them by a variant of lexicographical order. For example if one decides to order the alphabet by

X > Y > ...

and also to look at higher terms first, that means ordering

... > X³ > X² > X

and also

X > Y^k for all k.

There is some flexibility in ordering monomials, and this can be exploited in Gröbner basis theory.

[edit] Variations

[edit] Reverse lexicographic order

In a common variation of lexicographic order, one compares elements by reading from the right instead of from the left. For example, in reverse lexicographic order on monomials in three variables,

x y 3 z 2 < y z 2

This is not simply the order opposite to lexicographic. For example, $x y z < x y 2$ in both lexicographic and reverse lexicographic orders. A list of words so arranged is called a reverse lexicon, often confused with a rhyming dictionary.

Category: Order theory

Lexicographical order

From Wikipedia, the free encyclopedia

Contents

[edit] Case of multiple products

[edit] Ordering of strings

[edit] Monomials

[edit] Variations

[edit] Reverse lexicographic order

[edit] See also

Views

Navigation

interaction

Search

In other languages