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 [All88]:

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 [All88] (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 and large integers [AKS21] efficiently.
 
Thanks to njh for reminding me of an old problem -- LA, 8/2012.

References

[All88] L. Allison, 'Some Applications of Continuations', Computer Journal, 31(1), pp.9-11, doi:10.1093/comjnl/31.1.9, February 1988.

[AKS21] L. Allison, A. S. Konakurthu & D. F. Schmidt, 'On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond', Data Compression Conference, IEEE, pp.313-322, doi:10.1109/DCC50243.2021.000399, March 2021.
Also see Universal Codes.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Wednesday, 08-Feb-2023 07:58:23 UTC.

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