Ok, here it is again (strange cut-and-paste from my browser): www.1stworks.com/ref/RuskeyCombGen.pdf On Sun, May 26, 2013 at 11:45 AM, Mike Stay <metaweta@gmail.com> wrote:
Get rid of the asterisks.
On Sun, May 26, 2013 at 8:59 AM, Victor Miller <victorsmiller@gmail.com> wrote:
Ruskey has a wonderful book called "Combinatorial Generation" : www.1stworks.com/ref/*Ruskey*CombGen.pdf which is only available online. I don't know why it hasn't been published.
Victor
On Sun, May 26, 2013 at 10:50 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Ruskey claims constant _amortised_ time, not constant. But he also claims single transpositions between successive bracketings, which I certainly hadn't got around even to thinking about. Thanks!
WFL
On 5/26/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
Some neat-looking (if opaque) functional algorithms under A014486 !
But --- without having actually managed to understand most of them --- I'll stick my neck out and assert that these fall somewhat short of my objective: by constructing each new bracketing from scratch, they all cost time (at least) linear in n , as opposed to average constant.
Agreed? WFL
On 5/26/13, Wouter Meeussen <wouter.meeussen@telenet.be> wrote:
A014486 "List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's. ";
in short: cat[n_] := (2 n)!/n!/(n + 1)!; tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]; nexttree[t_] := Flatten[Reverse[t] /. {a___, 0, 0, 1, b___} :> Reverse[{Sort[{a, 0}] // Reverse, 1, 0, b}]]; wood[n_ /; n < 8] := NestList[nexttree, tree[n], cat[n] - 1];
and "wood[4]" then produces {{1, 1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 1, 0, 0, 0}, {1, 1, 1, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 0, 1, 0}, {1, 1, 0, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 0, 1, 0, 0}, {1, 1, 0, 1, 0, 0, 1, 0}, {1, 1, 0, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 1, 0, 1, 0}, {1, 0, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 0, 1, 0}, {1, 0, 1, 0, 1, 1, 0, 0}, {1, 0, 1, 0, 1, 0, 1, 0}}
close enough?
Wouter.
-----Original Message----- From: Fred lunnon Sent: Sunday, May 26, 2013 10:35 AM To: math-fun Subject: [math-fun] Bracketings (where's David Gries when I need him?)
[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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun