View source for Lexicographic and colexicographic order

[[w:Lexicographical order|Lexicographic]] (Lex) and [[w:Colexicographical order|colexicographic]] (CoLex) order are probably the most important ways to order [[w:Tuple|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.

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''.

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

They can also be reflected (see [http://oeis.org/wiki/File:Orderings;_6_choose_3.svg '''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 [[#reflections redundancy|'''below''']]).

==Combinations==

The sequence of the <math>\scriptstyle \binom{n}{k}</math> ''k''-subsets of <math>\scriptstyle \{1,\ldots,n\}</math> in CoLex order<br>
is the beginning of the infinite sequence of ''k''-subsets of <math>\scriptstyle \{1,2,3,\ldots\}</math> in CoLex order.<br>
This corresponds to the increasing sequence {{oeis|A014311}} = 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.

{| style="width:100%"
|-
|style="vertical-align:top;" rowspan="2"|[[File:Orderings; 6 choose 3.svg|thumb|center|400px|The <math>\scriptstyle \binom{6}{3} = 20</math> 3-subsets of <math>\scriptstyle \{1,\ldots,6\}</math>]]
|style="vertical-align:top;"|[[File:Orderings; 6 choose 3; even sum.svg|thumb|center|400px|The 10 3-subsets of <math>\scriptstyle \{1,...,6\}</math> with an even sum of elements]]
|-
|[[File:Combinations without repetition; 5 choose 3.svg|thumb|center|250px|The <math>\scriptstyle \binom{5}{3} = 10</math> 3-subsets of <math>\scriptstyle \{1,...,5\}</math><br><small>(binary vectors RevLex, combinations Lex)</small><br>This sequence of combinations is not the beginning of the sequence of combinations in Lex order in the file on the left.]]
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #cccccc;background:white"
! bgcolor="#dddddd"|Combinations with repetition
|-
|
[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|right|570px|The <math>\scriptstyle \left(\!\!{5\choose 3}\!\!\right) = \binom{5+3-1}{3} = \binom{7}{3} = 35</math> 3-submultisets of <math>\scriptstyle \{1,...,5\}</math><br><small>(red vectors RevLex, combinations Lex)</small>]]
|}

[[File:8 choose 2 array.svg|thumb|250px|right|2-subsets of the integers]]
The triangle on the right shows 2-subsets of the integers.<br>
This corresponds to the sequence {{oeis|A018900}} [[oeis:A018900/table|as a square array]].<br>
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)...

{| class="collapsible collapsed" style="border: 1px solid #cccccc;"
! bgcolor="#dddddd"|The 28 2-subsets of {1..8}
|-
|
     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 [[w:Permutation|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.<br>
This above all means the finitary symmetric group on <math>\mathbb{N}</math>, which is the union of all finite symmetric groups, and thus contains each finitary permutation of <math>\mathbb{N}</math>.<br>
Its ''n''-th element (counted from 0) is found in row ''n'' of {{oeis|A055089}}.

This makes it possible to assign a number to a permutation that is only given in cycle notation, without seeing it as a permutation of a particular number of elements.<br>
The reverse colex rank is its [[Inversion_(discrete_mathematics)#Inversion_related_vectors|left inversion count]] interpreted as a ([[w:endianness|little-endian]]) [[w:Factorial number system|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.

{| style="width:100%"
|-
|style="vertical-align:top;" rowspan="2"|[[File:Orderings; permutations 5-cycle.svg|thumb|center|400px|The 24 permutations of <math>\scriptstyle \{1,...,5\}</math><br>that have a complete [[Permutations by cycle type|5-cycle]] ]]
|style="vertical-align:top;"|[[File:Orderings; even permutations 4.svg|thumb|center|400px|The 12 even permutations of <math>\scriptstyle \{1,...,4\}</math><br><small>(the ones that are not green or orange in the table on the right)</small>]]
|style="vertical-align:top;" rowspan="2"|[[File:Symmetric group 4; permutation list.svg|thumb|center|200px|The 24 permutations of <math>\scriptstyle \{1,...,4\}</math> in RevCoLex order (reflected factorial numbers shown below)<br><br>This is the top left submatrix of all bigger tables of this kind (compare [http://oeis.org/A198380/a198380_1.txt '''this'''] one).]]
|-
|style="vertical-align:top;"|[[File:Orderings; even permutations 4; some.svg|thumb|center|400px|Some permutations of <math>\scriptstyle \{1,...,4\}</math><br>Here the blue patterns are not horizontally symmetric.]]
|}

<div id="reflections redundancy">
{| class="collapsible collapsed" style="width: 100%; border: 1px solid #cccccc;background:white"
! bgcolor="#dddddd"|Reflections are redundant
|-
|
[[File:Orderings; even permutations 4; redundant.svg|thumb|center|500px|]]
|}
</div>

==Partitions==
Infinite orderings of [[w:Partition (number theory)|integer partitions]] and [[w:Partition of a set|set partitions]] can be defined using CoLex ordering.
{| style="width:100%"
|-
|style="vertical-align:top;"|[[File:Partitions of 10.svg|thumb|center|370px|Partitions of 10<br><br>The binary vectors are in CoLex order and correspond to the increasing sequence {{oeis|A194602}} = 0,1,3,5,7,11,15...]]
|style="vertical-align:top;"|[[File:Orderings; set partitions 4.svg|thumb|center|450px|Partitions of a 4-set<br><br>The binary matrix in CoLex order<br>is the top left corner of the right matrix in the box below.]]
|}

{| class="collapsible collapsed" style="width: 100%; border: 1px solid #cccccc;background:white"
! colspan="2" bgcolor="#dddddd"|Partitions of a 5-set
|-
| The rows of the binary matrices are in CoLex order. (The white fields are 0s, colored fields are 1s.<br>
|-
| [[File:Set partitions 5; list.svg|thumb|center|300px]]
| [[File:Set partitions 5; list; blocks in binary.svg|thumb|center|600px]]
|}


==Walsh functions==
The rows of binary [[w:Walsh matrix|Walsh matrices]] in Lex and CoLex order give symmetric matrices.<br>
For normal Walsh matrices (with 1 and −1 instead of 0 and 1) RevLex and RevCoLex would give this result.<br>
{| style="width:100%"
|-
|style="vertical-align:top;"|[[File:Walsh 16 lexicographical.svg|thumb|center|400px|Lex<br>The arguments <small>(read like binary vectors)</small> are in Lex order.]]
|style="vertical-align:top;" rowspan="2"|[[File:Walsh 16 colexicographical.svg|thumb|center|400px|CoLex]]
|-
|style="vertical-align:top;"|[[File:Variadic logical XOR.svg|thumb|center|300px|Natural order<br>The arguments <abbr title="(read like binary vectors)"><small>(r.l.b.v.)</small></abbr> are in CoLex order.]]
|
|}


==Subsets==

{| style="width:100%"
|style="vertical-align:top;"| [[File:Subsets of 4-set with permutation, lexicographic.svg|thumb|center|400px|Subsets in Lex order]]
|style="vertical-align:top;"| [[File:Subsets of 4-set with permutation, lexicographic reflected.svg|thumb|center|400px|Subsets ordered with the same pattern, but reflected<br>(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.<br>
The second part shows that Lex order is the same as binary CoLex order, when the subsets themselves are reversed.

<syntaxhighlight lang="python">
>>> 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
</syntaxhighlight>

{| style="width:100%"
|style="vertical-align:top;"| [[File:Walsh permutation wp( 1, 2, 4, 8).svg|thumb|center|400px|Subsets <abbr title="(read like binary vectors)"><small>(r.l.b.v.)</small></abbr> in CoLex order,<br>also the Lex order of the reversed subsets]]
|style="vertical-align:top;"| [[File:Walsh permutation wp( 8, 4, 2, 1).svg|thumb|center|400px|Subsets <abbr title="(read like binary vectors)"><small>(r.l.b.v.)</small></abbr> in Lex order]]
|}

==Hypercube faces==
[[File:Tesseract Schlegel numbered.png|thumb|right|325px|tesseract with numbered vertices]]
{{multiple image
 | align = right  | width = 160
 | image1 = Tesseract cube 1.png
 | image2 = Tesseract square 08.png
 | footer = cube 1 <small>([[c:Category:Tesseract Schlegel shadow with alternating vertex colors; cells|cat]])</small> and square 8 <small>([[c:Category:Tesseract Schlegel shadow with alternating vertex colors; faces|cat]])</small> in ''CoLex'' order
}}
The following lists show the vertices of the {{w|tesseract}}s {{w|Face_(geometry)#k-face|''k''-faces}} for ''k'' in {3, 2, 1}.<br>
<small>(The tesseract is the 4-dimensional {{w|hypercube}}, and has 8 cubic cells, 24 square faces, 32 edges and 16 vertices.)<br></small>
For the cubes ''Lex'' and ''CoLex'' are the same. The binary matrix on the right has rotational symmetry.<br>
For squares and edges the two orderings are shown separately. Their binary matrices are rotations of each other.

{| class="collapsible collapsed" style="border: 1px solid #cccccc;"
!colspan="3" bgcolor="#dddddd"| 8 cubes
|-
|
  0
  1
  2
  3
 
  4
  5
  6
  7
|
 [ 0,  1,  2,  3,  4,  5,  6,  7],
 [ 0,  1,  2,  3,  8,  9, 10, 11],
 [ 0,  1,  4,  5,  8,  9, 12, 13],
 [ 0,  2,  4,  6,  8, 10, 12, 14],
 
 [ 1,  3,  5,  7,  9, 11, 13, 15],
 [ 2,  3,  6,  7, 10, 11, 14, 15],
 [ 4,  5,  6,  7, 12, 13, 14, 15],
 [ 8,  9, 10, 11, 12, 13, 14, 15]
|
 1111 1111 .... ....
 1111 .... 1111 ....
 11.. 11.. 11.. 11..
 1.1. 1.1. 1.1. 1.1.
 
 .1.1 .1.1 .1.1 .1.1
 ..11 ..11 ..11 ..11
 .... 1111 .... 1111
 .... .... 1111 1111
|}

{| class="collapsible collapsed" style="border: 1px solid #cccccc;"
!colspan="7" bgcolor="#dddddd"| 24 squares
|-
!colspan="3" bgcolor="#dddddd"| Lex
|style="width:50px;"|
!colspan="3" bgcolor="#dddddd"| CoLex
|-
|
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
|
 [ 0,  1,  2,  3],
 [ 0,  1,  4,  5],
 [ 0,  1,  8,  9],
 [ 0,  2,  4,  6],
 [ 0,  2,  8, 10],
 [ 0,  4,  8, 12],
 [ 1,  3,  5,  7],
 [ 1,  3,  9, 11],
 [ 1,  5,  9, 13],
 [ 2,  3,  6,  7],
 [ 2,  3, 10, 11],
 [ 2,  6, 10, 14],
 [ 3,  7, 11, 15],
 [ 4,  5,  6,  7],
 [ 4,  5, 12, 13],
 [ 4,  6, 12, 14],
 [ 5,  7, 13, 15],
 [ 6,  7, 14, 15],
 [ 8,  9, 10, 11],
 [ 8,  9, 12, 13],
 [ 8, 10, 12, 14],
 [ 9, 11, 13, 15],
 [10, 11, 14, 15],
 [12, 13, 14, 15]
|
 1111 .... .... ....
 11.. 11.. .... ....
 11.. .... 11.. ....
 1.1. 1.1. .... ....
 1.1. .... 1.1. ....
 1... 1... 1... 1...
 .1.1 .1.1 .... ....
 .1.1 .... .1.1 ....
 .1.. .1.. .1.. .1..
 ..11 ..11 .... ....
 ..11 .... ..11 ....
 ..1. ..1. ..1. ..1.
 ...1 ...1 ...1 ...1
 .... 1111 .... ....
 .... 11.. .... 11..
 .... 1.1. .... 1.1.
 .... .1.1 .... .1.1
 .... ..11 .... ..11
 .... .... 1111 ....
 .... .... 11.. 11..
 .... .... 1.1. 1.1.
 .... .... .1.1 .1.1
 .... .... ..11 ..11
 .... .... .... 1111
|style="width:50px;"|
|
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
|
 [ 0,  1,  2,  3],
 [ 0,  1,  4,  5],
 [ 0,  2,  4,  6],
 [ 1,  3,  5,  7],
 [ 2,  3,  6,  7],
 [ 4,  5,  6,  7],
 [ 0,  1,  8,  9],
 [ 0,  2,  8, 10],
 [ 1,  3,  9, 11],
 [ 2,  3, 10, 11],
 [ 8,  9, 10, 11],
 [ 0,  4,  8, 12],
 [ 1,  5,  9, 13],
 [ 4,  5, 12, 13],
 [ 8,  9, 12, 13],
 [ 2,  6, 10, 14],
 [ 4,  6, 12, 14],
 [ 8, 10, 12, 14],
 [ 3,  7, 11, 15],
 [ 5,  7, 13, 15],
 [ 9, 11, 13, 15],
 [ 6,  7, 14, 15],
 [10, 11, 14, 15],
 [12, 13, 14, 15]
|
 1111 .... .... ....
 11.. 11.. .... ....
 1.1. 1.1. .... ....
 .1.1 .1.1 .... ....
 ..11 ..11 .... ....
 .... 1111 .... ....
 11.. .... 11.. ....
 1.1. .... 1.1. ....
 .1.1 .... .1.1 ....
 ..11 .... ..11 ....
 .... .... 1111 ....
 1... 1... 1... 1...
 .1.. .1.. .1.. .1..
 .... 11.. .... 11..
 .... .... 11.. 11..
 ..1. ..1. ..1. ..1.
 .... 1.1. .... 1.1.
 .... .... 1.1. 1.1.
 ...1 ...1 ...1 ...1
 .... .1.1 .... .1.1
 .... .... .1.1 .1.1
 .... ..11 .... ..11
 .... .... ..11 ..11
 .... .... .... 1111
|}

{| class="collapsible collapsed" style="border: 1px solid #cccccc;"
!colspan="7" bgcolor="#dddddd"| 32 edges
|-
!colspan="3" bgcolor="#dddddd"| Lex
|style="width:50px;"|
!colspan="3" bgcolor="#dddddd"| CoLex
|-
|
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
|
 [ 0,  1],
 [ 0,  2],
 [ 0,  4],
 [ 0,  8],
 [ 1,  3],
 [ 1,  5],
 [ 1,  9],
 [ 2,  3],
 [ 2,  6],
 [ 2, 10],
 [ 3,  7],
 [ 3, 11],
 [ 4,  5],
 [ 4,  6],
 [ 4, 12],
 [ 5,  7],
 [ 5, 13],
 [ 6,  7],
 [ 6, 14],
 [ 7, 15],
 [ 8,  9],
 [ 8, 10],
 [ 8, 12],
 [ 9, 11],
 [ 9, 13],
 [10, 11],
 [10, 14],
 [11, 15],
 [12, 13],
 [12, 14],
 [13, 15],
 [14, 15]
|
 11.. .... .... ....
 1.1. .... .... ....
 1... 1... .... ....
 1... .... 1... ....
 .1.1 .... .... ....
 .1.. .1.. .... ....
 .1.. .... .1.. ....
 ..11 .... .... ....
 ..1. ..1. .... ....
 ..1. .... ..1. ....
 ...1 ...1 .... ....
 ...1 .... ...1 ....
 .... 11.. .... ....
 .... 1.1. .... ....
 .... 1... .... 1...
 .... .1.1 .... ....
 .... .1.. .... .1..
 .... ..11 .... ....
 .... ..1. .... ..1.
 .... ...1 .... ...1
 .... .... 11.. ....
 .... .... 1.1. ....
 .... .... 1... 1...
 .... .... .1.1 ....
 .... .... .1.. .1..
 .... .... ..11 ....
 .... .... ..1. ..1.
 .... .... ...1 ...1
 .... .... .... 11..
 .... .... .... 1.1.
 .... .... .... .1.1
 .... .... .... ..11
|style="width:50px;"|
|
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
|
 [ 0,  1],
 [ 0,  2],
 [ 1,  3],
 [ 2,  3],
 [ 0,  4],
 [ 1,  5],
 [ 4,  5],
 [ 2,  6],
 [ 4,  6],
 [ 3,  7],
 [ 5,  7],
 [ 6,  7],
 [ 0,  8],
 [ 1,  9],
 [ 8,  9],
 [ 2, 10],
 [ 8, 10],
 [ 3, 11],
 [ 9, 11],
 [10, 11],
 [ 4, 12],
 [ 8, 12],
 [ 5, 13],
 [ 9, 13],
 [12, 13],
 [ 6, 14],
 [10, 14],
 [12, 14],
 [ 7, 15],
 [11, 15],
 [13, 15],
 [14, 15]
|
 11.. .... .... ....
 1.1. .... .... ....
 .1.1 .... .... ....
 ..11 .... .... ....
 1... 1... .... ....
 .1.. .1.. .... ....
 .... 11.. .... ....
 ..1. ..1. .... ....
 .... 1.1. .... ....
 ...1 ...1 .... ....
 .... .1.1 .... ....
 .... ..11 .... ....
 1... .... 1... ....
 .1.. .... .1.. ....
 .... .... 11.. ....
 ..1. .... ..1. ....
 .... .... 1.1. ....
 ...1 .... ...1 ....
 .... .... .1.1 ....
 .... .... ..11 ....
 .... 1... .... 1...
 .... .... 1... 1...
 .... .1.. .... .1..
 .... .... .1.. .1..
 .... .... .... 11..
 .... ..1. .... ..1.
 .... .... ..1. ..1.
 .... .... .... 1.1.
 .... ...1 .... ...1
 .... .... ...1 ...1
 .... .... .... .1.1
 .... .... .... ..11
|}

As usual, the ''CoLex'' order is the one where the sequence for a lower dimension is the beginning of the sequence for a higher one.<br>
The binary matrices shown above can be interpreted as integer sequences:

'''vertices:''' 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768...<br>
'''edges:''' 3, 5, 10, 12, 17, 34, 48, 68, 80, 136, 160, 192, 257, 514, 768, 1028, 1280, 2056, 2560, 3072, 4112, 4352, 8224, 8704, 12288, 16448, 17408, 20480, 32896, 34816, 40960, 49152...<br>
'''squares:''' 15, 51, 85, 170, 204, 240, 771, 1285, 2570, 3084, 3840, 4369, 8738, 12336, 13056, 17476, 20560, 21760, 34952, 41120, 43520, 49344, 52224, 61440...<br>
'''cubes:''' 255, 3855, 13107, 21845, 43690, 52428, 61680, 65280...<br>
'''tesseracts:''' 65535...

===Petrie polygon===

A hypercube of dimension ''n'' has a {{w|Petrie polygon}} of size 2''n'', which is also the number of its {{w|Facet (geometry)|facets}}. It passes the first half of them in ascending order, and the second half in descending order.

{| class="collapsible collapsed" style="border: 1px solid #cccccc; text-align: center;"
!colspan="8" bgcolor="#ddd" | Petrie polygons for ''n'' = 2..4
|-
| [[File:Blue square, Gray equals Petrie.png|x300px]]
| [[File:Blue cube with Petrie polygon.png|x300px]]
| [[File:Tesseract Schlegel Petrie.png|x300px]]
|}

{| class="collapsible collapsed" style="border: 1px solid #cccccc; text-align: center;"
!colspan="8" bgcolor="#ddd" | cube faces
|-
| [[File:Cube square 0.png|150px]]<br>0
| [[File:Cube square 1.png|150px]]<br>1
| [[File:Cube square 2.png|150px]]<br>2
| [[File:Cube square 5.png|150px]]<br>5
| [[File:Cube square 4.png|150px]]<br>4
| [[File:Cube square 3.png|150px]]<br>3
|-
|colspan="8"| Each pair of consecutive edges belongs to one face.
|}

{| class="collapsible collapsed" style="border: 1px solid #cccccc; text-align: center;"
!colspan="8" bgcolor="#ddd" | tesseract cells
|-
| [[File:Tesseract cube 0.png|150px]]<br>0
| [[File:Tesseract cube 1.png|150px]]<br>1
| [[File:Tesseract cube 2.png|150px]]<br>2
| [[File:Tesseract cube 3.png|150px]]<br>3
| [[File:Tesseract cube 7.png|150px]]<br>7
| [[File:Tesseract cube 6.png|150px]]<br>6
| [[File:Tesseract cube 5.png|150px]]<br>5
| [[File:Tesseract cube 4.png|150px]]<br>4
|-
|colspan="8"| Each triple of consecutive edges belongs to one cell.
|}



<br style="clear: both;">

{{Commons|Category:Lexicographic and colexicographic order|Lexicographic and colexicographic order}}

[[Category:Mathematics]]