|
The research area of combinatorial generation is concerned with minimal-change orderings
for combinatorial objects of a particular type. For example, the binary reflected Gray code
orders the binary strings of length n such that each successive string differs from the previous
string in exactly one bit. As another example, a de Bruijn cycle is a string of length 2n that
contains each binary string of length n exactly once as a substring. Both concepts have had
numerous applications since their introduction in the mid-1940s, and are illustrated below
for n = 3
| 000, 001, 011, 010, 110, 111, 101, 100 | | 11101000. |
This talk introduces the cool-lex variation on lexicographic order. When applied to many
well-known combinatorial objects - including combinations, permutations, balanced parentheses,
necklaces with fixed-content, and so on - the result is a right-shift Gray code. This
means that each successive string differs from the previous string by shifting a single symbol
to the right. For example, the permutations of the multiset {1, 2, 2, 3} appear below in
cool-lex order
| 3221, 2213, 2123, 1223, 2231, 2321, 3212, 2132, 1232, 2312, 3122, 1322. |
Furthermore, there is a simple rule that determines each successive shift. Another application
of cool-lex order is in the construction of shorthand universal cycles, which are a natural
generalization of de Bruijn cycles. For example, the following string
contains the substrings 322, 221, 213, 132, … which are shorthand for the multiset permutations
3221, 2213, 2132, 1322, … of {1, 2, 2, 3} since the rightmost symbol is redundant and is
omitted. Shorthand universal cycles are easy to construct using cool-lex order, and provide
their first known construction.
The results in this talk are from my PhD thesis, which is under the supervision of Frank
Ruskey and Wendy Myrvold at the University of Victoria.
|