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 B_{n} of balanced parentheses strings with
n left and n right parentheses can be generated by prefix shifts.
If b_{1},b_{2},...,b_{2n}
is a member of B_{n}, then the kth
prefix shift is the string
b_{1}, b_{k}, b_{2}, ...,
b_{k1}, b_{k+1}, ...,
b_{2n}.
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.

The postscript file.

The pdf file.

Accepted at the
CATS
2008 conference in Wollongong, Australia.

For related algorithms, see
Back to list of publications.