# Lexicographic and colexicographic order

Lexicographic (Lex) and colexicographic (CoLex) order are probably the most important ways to order tuples in mathematics.

Lex order is that of a dictionary.

CoLex order is obtained by reflecting all tuples, applying Lex order, and reflecting the tuples again.

CoLex can also be obtained from Lex by reflecting all tuples and then reversing the order, or vice versa.

Lex order is more intuitive for most people.

CoLex order is more practical when the finite sets of tuples to be ordered shall be generalized to infinite sets of sequences. CoLex can be extended to natural numbers in a way that Lex cannot. Each r-subset of N has a finite rank under CoLex, whereas this is not the case under Lex. For example, ordering sets of natural numbers of size 3 by Lex, {2,3,4} comes after all sets whose lowest element is 1, which are infintely many.

Both orderings can be reversed, so there are actually four different orderings.

They can also be reflected (see here), but that's not a different ordering of the set of tuples, but just a certain ordering written in a different way.

When the set of tuples contains all reflections, each reflected order is equal to some of the four others (see below).

## Combinations

The sequence of the ${\displaystyle \scriptstyle {\binom {n}{k}}}$ k-subsets of ${\displaystyle \scriptstyle \{1,\ldots ,n\}}$ in CoLex order
is the beginning of the infinite sequence of k-subsets of ${\displaystyle \scriptstyle \{1,2,3,\ldots \}}$ in CoLex order.
This corresponds to the increasing sequence = 7,11,13,14,19,21...

In the file on the left it can be seen that the blue patterns are horizontally reflected.

However, this is not the case in the file on the right, which shows only some of the subsets.

 The ${\displaystyle \scriptstyle {\binom {6}{3}}=20}$ 3-subsets of ${\displaystyle \scriptstyle \{1,\ldots ,6\}}$ The 10 3-subsets of ${\displaystyle \scriptstyle \{1,...,6\}}$ with an even sum of elements The ${\displaystyle \scriptstyle {\binom {5}{3}}=10}$ 3-subsets of ${\displaystyle \scriptstyle \{1,...,5\}}$(binary vectors RevLex, combinations Lex)This sequence of combinations is not the beginning of the sequence of combinations in Lex order in the file on the left.
2-subsets of the integers

The triangle on the right shows 2-subsets of the integers.
This corresponds to the sequence as a square array.
The sequence of numbers (3,5,6,9,10,12...) corresponds to the CoLex ordering of 2-subsets:

    1     2
1     3
2     3
1     4
2     4
3     4
1     5
2     5
3     5
4     5
1     6
2     6
3     6
4     6
5     6
1     7
2     7
3     7
4     7
5     7
6     7
1     8
2     8
3     8
4     8
5     8
6     8
7     8


## Permutations

Finite sets of permutations are often shown in lex order, but rev colex order has the advantage that it can be used to order an infinite number of permutations.
This above all means the finitary symmetric group on ${\displaystyle \mathbb {N} }$, which is the union of all finite symmetric groups, and thus contains each finitary permutation of ${\displaystyle \mathbb {N} }$.
Its n-th element (counted from 0) is found in row n of .

This makes it possible to assign a number to a permutation that is only given in cycle notation, whithout seeing it as a permutation of a particular number of elements.
The reverse colex rank is its left inversion count interpreted as a (little-endian) factorial number.

The reverse colex order of the permutations corresponds to the colex order of these left inversion counts, as seen in the following illustrations.

 The 24 permutations of ${\displaystyle \scriptstyle \{1,...,5\}}$that have a complete 5-cycle The 12 even permutations of ${\displaystyle \scriptstyle \{1,...,4\}}$(the ones that are not green or orange in the table on the right) The 24 permutations of ${\displaystyle \scriptstyle \{1,...,4\}}$ in RevCoLex order (reflected factorial numbers shown below)This is the top left submatrix of all bigger tables of this kind (compare this one). Some permutations of ${\displaystyle \scriptstyle \{1,...,4\}}$Here the blue patterns are not horizontally symmetric.

## Partitions

Infinite orderings of integer partitions and set partitions can be defined using CoLex ordering.

 Partitions of 10The binary vectors are in CoLex order and correspond to the increasing sequence = 0,1,3,5,7,11,15... Partitions of a 4-setThe binary matrix in CoLex orderis the top left corner of the right matrix in the box below.

## Walsh functions

The rows of binary Walsh matrices in Lex and CoLex order give symmetric matrices.
For normal Walsh matrices (with 1 and −1 instead of 0 and 1) RevLex and RevCoLex would give this result.

 LexThe arguments (read like binary vectors) are in Lex order. CoLex Natural orderThe arguments (r.l.b.v.) are in CoLex order.

## Subsets

 Subsets in Lex order Subsets ordered with the same pattern, but reflected(This order does not seem to have a name.)

The following Python code shows the 16 subsets of the set {a,b,c,d} in lexicographic order.
The second part shows that Lex order is the same as binary CoLex order, when the subsets themselves are reversed.

>>> asc =  ['', 'a', 'b', 'ab', 'c', 'ac', 'bc', 'abc', 'd', 'ad', 'bd', 'abd', 'cd', 'acd', 'bcd', 'abcd']
>>> sorted(asc)
['', 'a', 'ab', 'abc', 'abcd', 'abd', 'ac', 'acd', 'ad', 'b', 'bc', 'bcd', 'bd', 'c', 'cd', 'd']

>>> desc = ['', 'a', 'b', 'ba', 'c', 'ca', 'cb', 'cba', 'd', 'da', 'db', 'dba', 'dc', 'dca', 'dcb', 'dcba']
>>> print desc == sorted(desc)
True

 Subsets (r.l.b.v.) in CoLex order,also the Lex order of the reversed subsets Subsets (r.l.b.v.) in Lex order