TOPICS

# Lexicographic Order

An ordering for the Cartesian product of any two sets and with order relations and , respectively, such that if and both belong to , then iff either

1. , or

2. and .

The lexicographic order can be readily extended to cartesian products of arbitrary length by recursively applying this definition, i.e., by observing that .

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 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 in lexicographic order are , , , , , , , .

Lexicographic order is sometimes called dictionary order.

Order, Monomial Order, Transposition Order

## Explore with Wolfram|Alpha

More things to try:

## 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 Web Resource. https://mathworld.wolfram.com/LexicographicOrder.html