An Eades-McKay algorithm for well-formed parentheses strings

Let T(n) be the set of all well-formed parentheses strings of length 2n. We show that the elements of T(n) 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 well-known Eades-McKay (1984) 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. (C) 1998 Elsevier Science B.V. All rights reserved.