An Eades-McKay Algorithm for Well-Formed Parentheses Strings

Abstract:

Let T(n,k) be the set of all well-formed 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 well-known Eades-McKay^* 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, well-formed parentheses string.
AMS Classification: 05A15, 05C30, 60J10, 68Q25, 68R05, 68R15.

• The postscript file is 158620 bytes, the dvi file is 26808 bytes.
• Please send me a note if you download a copy -- Thanks!
• Appeared in Information Processing Letters 68 (1998) 255-259.
• The reference to (^*) above is the paper: P. Eades and B. McKay, An Algorithm for Generating Subsets of Fixed Size with a Strong Minimal Change Property, Information Processing Letters, 19 (1984) 131-133.
• MR 99h:68127 (68R05).