Matched brackets (parentheses)

LA home
  N-Queens 3D

also see
  in Pascal
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(); };


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

         b( beforeOpen, i, closeQ );

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

   b(start, n, finish);

   return count;
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, S1..i, of a sequence, S1..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.
www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Wednesday, 18-May-2022 10:33:30 UTC.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.