Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order
verfasst von : Stephane Durocher, Pak Ching Li, Debajyoti Mondal, Aaron Williams
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A binary string
B
of length
n
=
k
t
is a
k
-ary Dyck word if it contains
t
copies of 1, and the number of 0s in every prefix of
B
is at most
k
−1 times the number of 1s. We provide two loopless algorithms for generating
k
-ary Dyck words in cool-lex order: (1) The first requires two index variables and assumes
k
is a constant; (2) The second requires
t
index variables and works for any
k
. We also efficiently rank
k
-ary Dyck words in cool-lex order. Our results generalize the “coolCat” algorithm by Ruskey and Williams (
Generating balanced parentheses and binary trees by prefix shifts
in CATS 2008) and provide the first loopless and ranking applications of the general cool-lex Gray code by Ruskey, Sawada, and Williams (
Binary bubble languages and cool-lex order
under review).