Ranking and Unranking of Well-formed Parenthesis String: A Unified Approach
Ro-yu Wu,Jou-Ming Chang, An-Hang Chen and Chun-Liang Liu* Author for corresponding; e-mail address: spade@mail.ntcb.edu.tw
Volume: Vol.39 No.4 (OCTOBER 2012)
Research Article
DOI:
Received: 20 June 2011, Revised: -, Accepted: 27 April 2012, Published: -
Citation: Wu R., Chang J., Chen A. and Liu C., Ranking and Unranking of Well-formed Parenthesis String: A Unified Approach, Chiang Mai Journal of Science, 2012; 39(4): 648-659.
Abstract
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 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.