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, n≥1,
- 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.
- then it must be of the form "(" [i] ")" [n-i-1],
1. By Continuations
n=0 . ~ "" n=5 . / \ . . | ~ "()((()()))" . / \ . . etc.
- A solution using continuations [All88]:
function brackets(n) { var count = 0; function start(p) { print(cols(++count,3)+": \""); p(); } function finish() { print("\"\n"); }; function b(before, n, after) { var i; function bPlus(q) { function beforeOpen(p) { function openP() { print("("); p(); }; before(openP); };//beforeOpen() function closeQ() { print(")"); q(); }; b( beforeOpen, i, closeQ ); };//bPlus(q) if( n==0 /*done*/) before( after ); 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.
- 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.
2. By Choices
- A more conventional "choosing" algorithm:
function brackets2(n) { var count=0, state=new Array(); function b(depth, nOpen, nClose) { if( nOpen+nClose <= 0 ) // done, have a solution { print(cols(++count,3)+': "'); for( var i = 0; i < depth; i ++ ) print(state[i]); println('"'); } else { if( nOpen > 0 ) { state[depth] = "("; b(depth+1,nOpen-1,nClose); } if( nClose > nOpen ) { state[depth] = ")"; b(depth+1,nOpen,nClose-1); } } }//b(depth,nOpen,nClose) b(0, n, n); return count; }//brackets2(n)
- The key point is that at the start of b(,,) no prefix of state[0..depth-1] contains more ")"s than "("s.
3. 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.
- And other publications.