An EadesMcKay Algorithm for WellFormed Parentheses Strings
Bette Bultena,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Let T(n,k) be the set of all wellformed parentheses
strings of length 2n with leftmost right parenthesis in position
k+1.
We show that the elements of T(n,k) can be listed
so that successive strings differ by the transposition of a left
and a right parenthesis.
Furthermore, between the two parentheses
that are transposed, only left parentheses occur.
Our listing is a modification of the wellknown
EadesMcKay^{*}
algorithm for generating combinations.
Like that algorithm, ours generates strings from the lexicographically
greatest string to the lexicographically least and can be implemented so that
each string is generated in constant time, in an amortized sense.
Keywords:
Combinatorial generation, wellformed parentheses string.
AMS Classification: 05A15, 05C30, 60J10, 68Q25, 68R05, 68R15.
Selected Citations:

Timothy Walsh,
Generating Gray Codes in O(1) WorstCase Time per Word,
Lecture Notes in Computer Science, 2731, 2003, pp. 73  89,
Discrete Mathematics and Theoretical Computer Science:
4th International Conference, DMTCS 2003 Dijon, France.

Hayadeh Ahrabian and Abbas NowzariDalini,
Generation of binary trees in Border from (01) Sequences,
Malaysian Journal of Computer Science, Vol. 17 No. 1, June 2004, pp. 2431

Donnacha Daly,
Efficient MultiCarrier Communication on the Digital Subscriber Loop,
Ph.D. Thesis,
Department of Electrical and Electronic Engineering,
University College, Dublin, Ireland, 2003.
Back to list of publications.