Cool-lex order and k-ary Catalan structures

详细信息    查看全文

• 作者：Stephane Durocher ; Pak Ching Li ; Debajyoti Mondal ; Frank Ruskey ; Aaron Williams
• 关键词：Catalan structures ; Cool-lex order ; Bubble langauges ; Loopless algorithms ; Ranking ; k-ary Dyck words ; k-ary trees
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 出版时间：October, 2012
• 年：2012
• 卷：16
• 期：Complete
• 页码：287-307
• 全文大小：704 K

文摘

For any given k, the sequence of k-ary Catalan numbers, , enumerates a number of combinatorial objects, including k-ary Dyck words of length 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 -ary Dyck words to obtain the stated efficiency.