Discrete Mathematics and Optimization Seminar
Jan. 14th, 2009
MC 320, 4:00PM
Gray codes and de Bruijn cycles using shifts
Aaron Williams
University of Victoria
In the upcoming volume of "The Art of Computer Programming", Don Knuth devotes 400 pages to the important topic of combinatorial generation. Mathematically, the research area asks which combinatorial objects can be ordered by which basic operations. For example, when the combinatorial object is binary strings of length n, and the operation is changing the value of a single bit, then an affirmative answer is provided by the binary reflected Gray code (1946). Similarly, if the operation is removing the leftmost bit and inserting a new rightmost bit, then an affirmative answer is provided by a de Bruijn cycle (1945). As a last example, permutations of any set can be ordered by swapping adjacent elements by the Johnson-Trotter-Steinhaus order (1963). Algorithmically, the research area asks how efficiently these orders can be generated.
This talk presents surprising new results for a number of well-studied combinatorial objects. Algorithmic highlights include the first O(1)-time O(1)-space algorithm for generating the permutations of any multi-set, and the fastest algorithm for creating balanced parentheses strings (determined by third-party tests). Mathematical highlights include the first shift Gray code for ordered trees, the first Gray code of any kind for necklaces, and the first generalization of de Bruijn cycles to multiset permutations. All of the results are based on a new variation of lexicographic order for fixed-content languages known as cool-lex order. In this variation, successive strings always differ by shifting a single symbol to the left.