Dear Fred, Here's what you want: Generating binary trees by transpositions: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.4560 It's constant time per tree (not just amortized). Victor On Sun, May 26, 2013 at 4:35 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
[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]
################################################################################
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun