
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 JohnsonTrotterSteinhaus order (1963). Algorithmically, the research area asks how efficiently these orders can be generated.
This talk presents surprising new results for a number of wellstudied combinatorial objects. Algorithmic highlights include the first O(1)time O(1)space algorithm for generating the permutations of any multiset, and the fastest algorithm for creating balanced parentheses strings (determined by thirdparty 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 fixedcontent languages known as coollex order. In this variation, successive strings always differ by shifting a single symbol to the left.



