Generating balanced parenthesis strings by prefix shifts

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Aaron Williams, Department of Computer Science, University of Victoria, Canada.

Abstract:

We show that the set Bn of balanced parentheses strings with n left and n right parentheses can be generated by prefix shifts. If b1,b2,...,b2n is a member of Bn, then the k-th prefix shift is the string b1, bk, b2, ..., bk-1, bk+1, ..., b2n. Prefix shift algorithms are also known for combinations, and permutations of a multiset; the combination algorithm appears in fascicles of Knuth, vol. 4. We show that the algorithm is closely related to the combination algorithm, and like it, has a loopless implementation, and a ranking algorithm that uses O(n) arithmetic operations. Additionally, the algorithm can be directly translated to generate all binary trees by a loopless implementation that makes a constant number of pointer changes for each successively generated tree.