Cool-lex Order and <I>k</I>-ary Catalan Structures

Cool-lex Order and k-ary Catalan Structures

Stephane Durocher, Department of Computer Science, University of Manitoba, Canada.
Pak Ching Li, Department of Computer Science, University of Manitoba, Canada.
Debajyoti Mondal, Department of Computer Science, University of Manitoba, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Aaron Williams, Department of Mathematics and Statistics, McGill University.

Abstract:

For any given k, the sequence of k-ary Catalan numbers, C_{t,k} = \frac{1}{kt+1}\binom{kt}{t}, enumerates a number of combinatorial objects, including k-ary Dyck words of length n=kt and k-ary trees with t internal nodes. We show that these objects can be efficiently ordered using the same variation of lexicographic order known as cool-lex order. In particular, we provide loopless algorithms that generate each successive object in O(1) time. The algorithms are also efficient in terms of memory, with the k-ary Dyck word algorithm using O(1) additional index variables, and the k-ary tree algorithm using O(t) additional pointers and index variables. We also show how to efficiently rank and unrank k-ary Dyck words in cool-lex order using O(kt) arithmetic operations, subject to an initial precomputation. Our results are based on the cool-lex successor rule for sets of binary strings that are bubble languages. However, we must complement and reverse 1/k-ary Dyck words to obtain the stated efficiency.

This paper is an updated and improved version of the combination of two conference papers: (a) F. Ruskey and Aaron Williams, Generating Balanced Parentheses and Binary Trees by Prefix Shifts; (b) Stephane Durocher, Pak Ching Li, Debajyoti Mondal, and Aaron Williams. Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order.
The driving force behind these papers: Aaron Williams.
The pdf file.
Submitted to the Journal of Discrete Algorithms.
Accepted by the Journal of Discrete Algorithms, April 30, 2012.
For the paper where cool-lex order was first introduced, see coollex.

Back to list of publications.