Lexicographic Order

An ordering for the Cartesian product 👁 ×
of any two sets 👁 A
and 👁 B
with order relations 👁 <A
and 👁 <B
, respectively, such that if 👁 (a_1,b_1)
and 👁 (a_2,b_2)
both belong to 👁 A×B
, then 👁 (a_1,b_1)<(a_2,b_2)
iff either

1. 👁 a_1<Aa_2
, or

2. 👁 a_1=a_2
and 👁 b_1<Bb_2
.

The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that 👁 A×B×C=A×(B×C)
.

When applied to permutations, lexicographic order is increasing numerical order (or equivalently, alphabetic order for lists of symbols; Skiena 1990, p. 4). For example, the permutations of 👁 {1,2,3}
in lexicographic order are 123, 132, 213, 231, 312, and 321.

When applied to subsets, two subsets are ordered by their smallest elements (Skiena 1990, p. 44). For example, the subsets of 👁 {1,2,3}
in lexicographic order are 👁 {}
, 👁 {1}
, 👁 {1,2}
, 👁 {1,2,3}
, 👁 {1,3}
, 👁 {2}
, 👁 {2,3}
, 👁 {3}
.

Lexicographic order is sometimes called dictionary order.

See also

Order, Monomial Order, Transposition Order

Explore with Wolfram|Alpha

References

Ruskey, F. "Information on Combinations of a Set." http://www.theory.csc.uvic.ca/~cos/inf/comb/CombinationsInfo.html.Séroul, R. Programming for Mathematicians. Berlin: Springer-Verlag, p. 23, 2000.Skiena, S. "Lexicographically Ordered Permutations" and "Lexicographically Ordered Subsets." §1.1.1 and 1.5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 3-5 and 43-44, 1990.

Referenced on Wolfram|Alpha

Lexicographic Order

Cite this as:

Weisstein, Eric W. "Lexicographic Order." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LexicographicOrder.html

Subject classifications