Ranking and Unranking of Well-formed Parenthesis Strings: A Unified Approach

作者：Wu Ro Yu; Chang Jou Ming^*; Chen An Hang; Liu Chun Liang

来源：Chiang Mai Journal of Science, 2012, 39(4): 648-659.

• ranking algorithms
• unranking algorithms
• well-formed parenthesis strings
• lexicographic order

A string s of length 2n is called a well-formed parenthesis string (w.f.p. string for short), if it consists of n left parentheses and n right parentheses such that no prefix of s contains more right parentheses than left parentheses. W.f.p. strings are represented in the literature by different types of integer sequences including P-, X-, and T-sequences. In this paper, we introduce a new class of sequences, called L-sequences, which originates from the so-called RD-sequences for representing k-ary trees and their generalization, called non-regular trees. This paper deals with the ranking and unranking of w.f.p. strings in lexicographic order under these representations. We give linear-time transformations between L-sequences and other type of sequences, and design linear time ranking and unranking algorithms for all these sequence types.

• 出版日期2012-10