[This may well be buried deep in Knuth's Art of Programming, or Arndt's fxtbook. But it proved a humbling exercise for this old coder, so I'm going to inflict it on everybody anyway.] The problem: given natural n , to generate in turn all sequences of n matched pairs of brackets; alternatively, ordered rooted trees with n+1 nodes, etc. --- see OEIS A000108. The solution should cost space linear in n , and (amortised) time constant per "bracketing" generated. My own current best effort below, hewed painfully from solid Maple, should give the general idea. [It employs a function with side-effects --- unavailable in some other languages, but easily circumvented.] While I suppose it's reasonably acceptable, I'm far from satisfied with all that fiddling with pointers that goes on in the middle. Can anybody manage something more elegant? Fred Lunnon ################################################################################ # Catalan number C(n) via recursion cat_rec := proc (n) local i,j,cati,cat; cat := array(0..n); cat[0] := 1; for i from 0 to n-1 do cati := 0; for j from 0 to i do cati := cati + cat[j]*cat[i-j] od; cat[i+1] := cati od; cat[n] end; # Matchings of n pairs of brackets, in reverse of reversed alphabetic order: # Seek leftmost P = Q [R] S with l > 1 ; # if R non-final, advance R and initialise everything Q to its left; # else relocate [ right then initialise shorter R and longer Q ; # Initial = [[...]] , final = []...[] ; # Right-hand sentinel ...[[[]]] -> ...[[][]] -> [...][[]] ; # Initialise bracketing of length 2 n init_bracket := proc (n, P) local j,l; l := 3; P := array(1..n+n+l+l); for j from 0 to n-1 do P[1+j+j] := +1; P[2+j+j] := -1 od; for j from 0 to l-1 do P[n+n+1+j] := +1; P[n+n+1+l+j] := -1 od; NULL end; # Next bracketing after P[i1] onwards, qua sequence +1,-1 for [,] ; # return highest index i altered, or 0 if P was final; # halt on return = n+n+2, start on n+n+3; next_bracket := proc (i0, P) local i,i1,i2,j,k,d; # P0 = P1 [P2] with P2 nonempty, or P1 ] ; # i1 = start P1, i2 = 1 + end P1 ; i1 := i0; d := 0; i := i1-1; while d = 0 or d = 1 do i := i+1; d := d+P[i] od; if d >= 0 then k := next_bracket(i, P) fi; # advance P2 ? if d < 0 then # P0 was final ...] i1 := i1+1; # shorten [P1] on left i2 := i+1; k := 0 elif k = 0 then # P2 was final ...[[ i2 := i+1; # lengthen P1 on right k := i else i2 := i-1 fi; # usual path for j from 1 to (i2-i1)/2 do # initialise P1 P[i1+j-1] := +1; P[i2-j] := -1 od; k end; switch := true; # test bracketings if switch then n := 4; cat_rec(n); init_bracket(n, P); cter := 0: print(cter, convert(P, list)); # pre-initial while next_bracket(1, P) <> n+n+2 do cter := cter + 1; print(cter, convert(P, list)) od: cter := cter + 1: print(cter, convert(P, list)); # post-final fi; # 14 # 0, [1,-1,1,-1,1,-1,1,-1,1,1,1,-1,-1,-1] # 1, [1,1,1,1,-1,-1,-1,-1,1,1,-1,1,-1,-1] (((()))) # 2, [1,1,1,-1,1,-1,-1,-1,1,1,-1,1,-1,-1] ((()())) # 3, [1,1,-1,1,1,-1,-1,-1,1,1,-1,1,-1,-1] (()(())) # 4, [1,1,1,-1,-1,1,-1,-1,1,1,-1,1,-1,-1] ((())()) # 5, [1,1,-1,1,-1,1,-1,-1,1,1,-1,1,-1,-1] (()()()) # 6, [1,-1,1,1,1,-1,-1,-1,1,1,-1,1,-1,-1] ()((())) # 7, [1,-1,1,1,-1,1,-1,-1,1,1,-1,1,-1,-1] ()(()()) # 8, [1,1,-1,-1,1,1,-1,-1,1,1,-1,1,-1,-1] (())(()) # 9, [1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1] ()()(()) # 10, [1,1,1,-1,-1,-1,1,-1,1,1,-1,1,-1,-1] ((()))() # 11, [1,1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,-1] (()())() # 12, [1,-1,1,1,-1,-1,1,-1,1,1,-1,1,-1,-1] ()(())() # 13, [1,1,-1,-1,1,-1,1,-1,1,1,-1,1,-1,-1] (())()() # 14, [1,-1,1,-1,1,-1,1,-1,1,1,-1,1,-1,-1] ()()()() # 15, [1,1,1,1,1,-1,-1,-1,-1,-1,1,1,-1,-1] ################################################################################