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)