Lexicographical ordering

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 way the alphabetical order of words is based on the alphabetical order of their component letters. This generalization consists primarily in defining a total order over the sequences (often called words in computer science) of elements of a finite totally ordered set, often called alphabet.

There are several variants and generalizations of the lexicographical ordering. One 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. Another generalization defines an order on a Cartesian product of partially ordered sets; this order is a total order if and only if the factors of the Cartesian product are totally ordered.

The word lexicographic is derived from lexicon, the set of words that are used in some language and appear in dictionaries and encyclopedias. The lexicographic order has thus been introduced for sorting the entries of dictionaries and encyclopedias. This has been formalized in the following way.

Consider a finite set A, often called alphabet, which is totally ordered. In dictionaries, this is the common alphabet, ordered by the alphabetical order. In book indexes, the alphabet is generally extended to all alphanumeric characters; it is the object of a specific convention whether a digit is considered as smaller or larger than a letter. The lexicographic order is a total order on the sequences of elements of A, often called words on A, which is defined as follows.

...
Wikipedia