Ranking and unranking of well-formed parenthesis strings in diverse representations

摘要

Well-formed parenthesis (w.f.p.) strings can be represented by different types of integer sequences including P-sequences, X-sequences, and T-sequences. In this paper, we introduce a new class of sequences called L-sequences which comes from the so-called RD-sequences for representing k-ary trees. We then search out the relationships among these representations and deal with the problems of ranking and unranking of w.f.p. strings in lexicographic order under these diverse representations. A result shows that the ranking and unranking of w.f.p. strings can be done in O(n) time for all such representations, where n is the number of pairs of balanced parentheses.