Name
Abstract | ||
|---|---|---|
For any given k, the sequence of k-ary Catalan numbers, C"t","k=1kt+1(ktt), 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2012.04.015 | J. Discrete Algorithms |
Keywords | Field | DocType |
k-ary catalan structure,cool-lex successor rule,k-ary tree algorithm,k-ary tree,cool-lex order,additional index variable,k-ary dyck word,lexicographic order,k-ary catalan number,unrank k-ary dyck word,k-ary dyck word algorithm,ranking | Pointer (computer programming),Discrete mathematics,Catalan,Combinatorics,Ranking,Precomputation,Binary strings,Successor cardinal,Catalan number,Lexicographical order,Mathematics | Journal |
Volume | ISSN | Citations |
16, | 1570-8667 | 3 |
PageRank | References | Authors |
0.41 | 23 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephane Durocher | 1 | 342 | 42.89 |
| Pak Ching Li | 2 | 14 | 3.87 |
| Debajyoti Mondal | 3 | 93 | 27.33 |
| Frank Ruskey | 4 | 906 | 116.61 |
| Aaron Williams | 5 | 139 | 20.42 |