Generating Balanced Parentheses and Binary Trees by Prefix Shifts

Ruskey, F. and Williams, A.

We show that the set Bn of balanced parenthesis strings with n left and n right parentheses can be generated by prefix shifts. If b_1, b_2, . . . , b_{2n} is a mem- ber of B_n, then the k-th prefix shift is the string b_1, b_k, b_2, . . . , b_{k?1}, b_{k+1}, . . . , b_{2n}. Prefix shift algo- rithms are also known for combinations, and per- mutations 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 di- rectly translated to generate all binary trees by a loopless implementation that makes a constant num- ber of pointer changes for each successively generated tree.

Cite as: Ruskey, F. and Williams, A. (2008). Generating Balanced Parentheses and Binary Trees by Prefix Shifts. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 107-115.

(from crpit.com) (local if available)