|
- 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, 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.
|
|