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 conies from the so-called KD-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.
ranking algorithms unranking algorithms well-formed parenthesis strings lexicographic order
Ro-Yu Wu Jou-Ming Chang
Department of Industrial Management Lunghwa University of Science and Technology Taoyuan, Taiwan, RO Institute of Information and Decision Sciences National Taipei College of Business Taipei, Taiwan, R
国际会议
上海
英文
71-75
2011-03-11（万方平台首次上网日期，不代表论文的发表时间）