Matched brackets (parentheses)

Problem: Enumerate (generate) all sequences of 'n' pairs of matched brackets (parentheses), where n ≥ 0.

 

Note that if [n] is a solution for n pairs,

then it must be of the form   "(" [i] ")" [n-i-1],

where 0≤i<n, [i] is a solution for 'i' pairs, and [n-i-1] is a solution for 'n-i-1' pairs.

 

The problem is equivalent to generating all rooted, ordered, k-ary trees of n+1 nodes,

e.g., n=0,  .  ~   ( )

e.g., n=5,  .
           / \
          .   .
              |  ~ ( ()((()())) )
              .
             / \
            .   .

A solution using continuations:

function brackets(n)
 { var count = 0, seq = "";

   var start  = function(p)
    { seq = ""; p(); };

   var finish = function( )
    { print(cols(++count,3) + ": " + seq + ".\n"); };

   var b = function( before, n, after )
    { var i;

      var bPlus = function(q)
       {
	 var beforeOpen = function(p)
          { var openP = function( ) { seq+="("; p(); };

            before(openP);
          };//beforeOpen()

         var closeQ = function() { seq+=")"; q(); };

         b( beforeOpen, i, closeQ );
       };//bPlus(q)

      if( n == 0 ) before( after );  // done
      else
	 for( i = 0; i < n; i ++ )
            b( bPlus, n-i-1, after );
    };//b(before,n,after)

   b(start, n, finish);

   return count;
 }//brackets(n)

brackets(n)	is a wrapper.
b(before,n,after)	does most of the work.
before, and after	are continuations (functions) to be called in front of, and following, each solution for n.
bplus	is the continuation to call in front of each part-solution generated by b(bPlus, n-i-1, after)

 

If '(' < ')', the solutions are generated in reverse lexicographical order.

Exercise: Make them come out in lexicographical (alphabetic) order.

 

BTW, another angle on the problem is to generate all sequences of n '('s and n ')'s, such that every prefix, S_1..i, of a sequence, S_1..2n, contains at least as many '('s as ')'s. This recalls ways of encoding trees efficiently.

 

Thanks to njh for reminding me of an old problem -- LA, 8/2012.