Matched brackets (parentheses)

LA home
Computing
Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Subgraphs
  Brackets
  Self-Ref
  brackets

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,  .
           / \
          .   .
              |  ~ ( ()((()())) )
              .
             / \
            .   .
n=
count=
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, 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, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Thursday, 15-Apr-2021 10:50:48 EDT.

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