[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] ################################################################################
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
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
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
Fred, Here's another one by Ruskey et. al. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.8866 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
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
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
ranking and unranking those binary trees is also fun: NthTreeLocal[1 000 000 000] {1,1,0,1,1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,0,0,0,0,1,0,0,1,0,1,0} Wouter -----Original Message----- From: Mike Stay Sent: Sunday, May 26, 2013 5:45 PM To: math-fun Subject: Re: [math-fun] Bracketings (where's David Gries when I need him?) 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
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
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
* Fred lunnon <fred.lunnon@gmail.com> [May 27. 2013 19:53]:
[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
[...]
See http://jjj.de/fxt/demo/comb/index.html everything containing either of "catalan", "paren", or "dyck" may be interesting. In the fxt lib: ./src/comb/paren-gray.h ./src/comb/paren-lex.h ./src/comb/paren-pref.h ./src/comb/paren.h ./src/comb/catalan-gslex.h ./src/comb/catalan-path-lex.cc ./src/comb/catalan-path-lex.h ./src/comb/catalan-rgs-gray.h ./src/comb/catalan-rgs.h ./src/comb/catalan-step-rgs-colex.h ./src/comb/catalan-step-rgs-lex.h ./src/comb/catalan-step-rgs-subset-lexrev.h ./src/comb/catalan-subset-lex.h ./src/comb/catalan.h ./src/comb/dyck-gray.h ./src/comb/dyck-gray2.h ./src/comb/dyck-pref.h ./src/comb/dyck-pref2.h ./src/comb/dyck-rgs-subset-lex.h ./src/comb/dyck-rgs.h Everything "subset-lex" or "gray" is either already loopless (i.e. O(1) per update) or can be modified to be. Loopless algorithms for the "subset-lex" order come for free (when generating in backward order), with at most O(1) additional memory used. Example dyck-rgs-subset-lex-demo.cc, using dyck-rgs-subset-lex.h: arg 1: 5 == n [Length of RGS] default=4 arg 2: 2 == k [k-ary Dyck words, k>=2 (k==2 gives Catalan RGS).] default=3 arg 3: 0 == bw [Whether to generate backward order] default=0 1: [ . . . . . ] 1 1.1.1.1.1. 2: [ . 1 . . . ] 1 11..1.1.1. 3: [ . 1 1 . . ] 2 11.1..1.1. 4: [ . 1 2 . . ] 2 111...1.1. 5: [ . 1 2 1 . ] 3 111..1..1. 6: [ . 1 2 2 . ] 3 111.1...1. 7: [ . 1 2 3 . ] 3 1111....1. 8: [ . 1 2 3 1 ] 4 1111...1.. 9: [ . 1 2 3 2 ] 4 1111..1... 10: [ . 1 2 3 3 ] 4 1111.1.... 11: [ . 1 2 3 4 ] 4 11111..... 12: [ . 1 2 2 1 ] 4 111.1..1.. 13: [ . 1 2 2 2 ] 4 111.1.1... 14: [ . 1 2 2 3 ] 4 111.11.... 15: [ . 1 2 1 1 ] 4 111..1.1.. 16: [ . 1 2 1 2 ] 4 111..11... 17: [ . 1 2 . 1 ] 4 111...11.. 18: [ . 1 1 1 . ] 3 11.1.1..1. 19: [ . 1 1 2 . ] 3 11.11...1. 20: [ . 1 1 2 1 ] 4 11.11..1.. 21: [ . 1 1 2 2 ] 4 11.11.1... 22: [ . 1 1 2 3 ] 4 11.111.... 23: [ . 1 1 1 1 ] 4 11.1.1.1.. 24: [ . 1 1 1 2 ] 4 11.1.11... 25: [ . 1 1 . 1 ] 4 11.1..11.. 26: [ . 1 . 1 . ] 3 11..11..1. 27: [ . 1 . 1 1 ] 4 11..11.1.. 28: [ . 1 . 1 2 ] 4 11..111... 29: [ . 1 . . 1 ] 4 11..1.11.. 30: [ . . 1 . . ] 2 1.11..1.1. 31: [ . . 1 1 . ] 3 1.11.1..1. 32: [ . . 1 2 . ] 3 1.111...1. 33: [ . . 1 2 1 ] 4 1.111..1.. 34: [ . . 1 2 2 ] 4 1.111.1... 35: [ . . 1 2 3 ] 4 1.1111.... 36: [ . . 1 1 1 ] 4 1.11.1.1.. 37: [ . . 1 1 2 ] 4 1.11.11... 38: [ . . 1 . 1 ] 4 1.11..11.. 39: [ . . . 1 . ] 3 1.1.11..1. 40: [ . . . 1 1 ] 4 1.1.11.1.. 41: [ . . . 1 2 ] 4 1.1.111... 42: [ . . . . 1 ] 4 1.1.1.11.. Right column gives parens: "1" and "." for "(" and ")". Each update costs less than 10 CPU cycles. Here is lex order, paren-lex-demo.cc, using paren-lex.h: 1: ((((())))) 11111..... [ . 1 2 3 4 ] [ . 1 2 3 4 ] 0 2: (((()()))) 1111.1.... [ . 1 2 3 3 ] [ . 1 2 3 5 ] 4 3: (((())())) 1111..1... [ . 1 2 3 2 ] [ . 1 2 3 6 ] 4 4: (((()))()) 1111...1.. [ . 1 2 3 1 ] [ . 1 2 3 7 ] 4 5: (((())))() 1111....1. [ . 1 2 3 . ] [ . 1 2 3 8 ] 4 6: ((()(()))) 111.11.... [ . 1 2 2 3 ] [ . 1 2 4 5 ] 3 7: ((()()())) 111.1.1... [ . 1 2 2 2 ] [ . 1 2 4 6 ] 4 8: ((()())()) 111.1..1.. [ . 1 2 2 1 ] [ . 1 2 4 7 ] 4 9: ((()()))() 111.1...1. [ . 1 2 2 . ] [ . 1 2 4 8 ] 4 10: ((())(())) 111..11... [ . 1 2 1 2 ] [ . 1 2 5 6 ] 3 11: ((())()()) 111..1.1.. [ . 1 2 1 1 ] [ . 1 2 5 7 ] 4 12: ((())())() 111..1..1. [ . 1 2 1 . ] [ . 1 2 5 8 ] 4 13: ((()))(()) 111...11.. [ . 1 2 . 1 ] [ . 1 2 6 7 ] 3 14: ((()))()() 111...1.1. [ . 1 2 . . ] [ . 1 2 6 8 ] 4 15: (()((()))) 11.111.... [ . 1 1 2 3 ] [ . 1 3 4 5 ] 2 16: (()(()())) 11.11.1... [ . 1 1 2 2 ] [ . 1 3 4 6 ] 4 17: (()(())()) 11.11..1.. [ . 1 1 2 1 ] [ . 1 3 4 7 ] 4 18: (()(()))() 11.11...1. [ . 1 1 2 . ] [ . 1 3 4 8 ] 4 19: (()()(())) 11.1.11... [ . 1 1 1 2 ] [ . 1 3 5 6 ] 3 20: (()()()()) 11.1.1.1.. [ . 1 1 1 1 ] [ . 1 3 5 7 ] 4 21: (()()())() 11.1.1..1. [ . 1 1 1 . ] [ . 1 3 5 8 ] 4 22: (()())(()) 11.1..11.. [ . 1 1 . 1 ] [ . 1 3 6 7 ] 3 23: (()())()() 11.1..1.1. [ . 1 1 . . ] [ . 1 3 6 8 ] 4 24: (())((())) 11..111... [ . 1 . 1 2 ] [ . 1 4 5 6 ] 2 25: (())(()()) 11..11.1.. [ . 1 . 1 1 ] [ . 1 4 5 7 ] 4 26: (())(())() 11..11..1. [ . 1 . 1 . ] [ . 1 4 5 8 ] 4 27: (())()(()) 11..1.11.. [ . 1 . . 1 ] [ . 1 4 6 7 ] 3 28: (())()()() 11..1.1.1. [ . 1 . . . ] [ . 1 4 6 8 ] 4 29: ()(((()))) 1.1111.... [ . . 1 2 3 ] [ . 2 3 4 5 ] 1 30: ()((()())) 1.111.1... [ . . 1 2 2 ] [ . 2 3 4 6 ] 4 31: ()((())()) 1.111..1.. [ . . 1 2 1 ] [ . 2 3 4 7 ] 4 32: ()((()))() 1.111...1. [ . . 1 2 . ] [ . 2 3 4 8 ] 4 33: ()(()(())) 1.11.11... [ . . 1 1 2 ] [ . 2 3 5 6 ] 3 34: ()(()()()) 1.11.1.1.. [ . . 1 1 1 ] [ . 2 3 5 7 ] 4 35: ()(()())() 1.11.1..1. [ . . 1 1 . ] [ . 2 3 5 8 ] 4 36: ()(())(()) 1.11..11.. [ . . 1 . 1 ] [ . 2 3 6 7 ] 3 37: ()(())()() 1.11..1.1. [ . . 1 . . ] [ . 2 3 6 8 ] 4 38: ()()((())) 1.1.111... [ . . . 1 2 ] [ . 2 4 5 6 ] 2 39: ()()(()()) 1.1.11.1.. [ . . . 1 1 ] [ . 2 4 5 7 ] 4 40: ()()(())() 1.1.11..1. [ . . . 1 . ] [ . 2 4 5 8 ] 4 41: ()()()(()) 1.1.1.11.. [ . . . . 1 ] [ . 2 4 6 7 ] 3 42: ()()()()() 1.1.1.1.1. [ . . . . . ] [ . 2 4 6 8 ] 4 Best regards, jj
Having completed my exhausting survey of the competition for a lexicographic generator, I award myself a gallant third place (out of three) for elegance, and a narrow first for usability. Ruskey <BinTreeLex.c> and Arndt <paren-lex.h> both eschew recursion, and Arndt's very clean algorithm is somewhat shorter. However, he represents a bracketing only as a sequence of locations of left brackets: including updating the string itself would leave all three efforts approximately the same length. Ruskey falls over on special cases n = 1,2 --- hee-hee, who tested that program then? As to single transposition "Gray-code" generators, Ruskey <algorithm 5.16, binGray.c> provides an instructive pair of mutually recursive procedures which seem to work --- more than I can manage at the moment --- but which would be a nightmare to adapt to the co-routine / object-oriented model required by a large-scale modular application --- where the user needs to pull up the "next" thingy on demand, as opposed to building a bloat-load of the complete set beforehand. Arndt <paren-gray.h> does everything right (apart from actually telling the user how a bracketing is represented), quoting a reference Tadao Takaoka, Stephen Violich "Combinatorial Generation by Fusing Loopless Algorithms" which should repay further investigation. I'm motivated to reflect on the sad fact that recursion and co-routines are incompatible paradigms. Furthermore, while it is undoubtedly harder initially to write "loopless" (yerwot?) algorithms, they do seem in practice noticeably easier to debug than their recursive counterparts. Fred Lunnon On 5/27/13, Joerg Arndt <arndt@jjj.de> wrote:
* Fred lunnon <fred.lunnon@gmail.com> [May 27. 2013 19:53]:
[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
[...]
See http://jjj.de/fxt/demo/comb/index.html everything containing either of "catalan", "paren", or "dyck" may be interesting.
In the fxt lib: ./src/comb/paren-gray.h ./src/comb/paren-lex.h ./src/comb/paren-pref.h ./src/comb/paren.h
./src/comb/catalan-gslex.h ./src/comb/catalan-path-lex.cc ./src/comb/catalan-path-lex.h ./src/comb/catalan-rgs-gray.h ./src/comb/catalan-rgs.h ./src/comb/catalan-step-rgs-colex.h ./src/comb/catalan-step-rgs-lex.h ./src/comb/catalan-step-rgs-subset-lexrev.h ./src/comb/catalan-subset-lex.h ./src/comb/catalan.h
./src/comb/dyck-gray.h ./src/comb/dyck-gray2.h ./src/comb/dyck-pref.h ./src/comb/dyck-pref2.h ./src/comb/dyck-rgs-subset-lex.h ./src/comb/dyck-rgs.h
Everything "subset-lex" or "gray" is either already loopless (i.e. O(1) per update) or can be modified to be. Loopless algorithms for the "subset-lex" order come for free (when generating in backward order), with at most O(1) additional memory used.
Example dyck-rgs-subset-lex-demo.cc, using dyck-rgs-subset-lex.h:
arg 1: 5 == n [Length of RGS] default=4 arg 2: 2 == k [k-ary Dyck words, k>=2 (k==2 gives Catalan RGS).] default=3 arg 3: 0 == bw [Whether to generate backward order] default=0 1: [ . . . . . ] 1 1.1.1.1.1. 2: [ . 1 . . . ] 1 11..1.1.1. 3: [ . 1 1 . . ] 2 11.1..1.1. 4: [ . 1 2 . . ] 2 111...1.1. 5: [ . 1 2 1 . ] 3 111..1..1. 6: [ . 1 2 2 . ] 3 111.1...1. 7: [ . 1 2 3 . ] 3 1111....1. 8: [ . 1 2 3 1 ] 4 1111...1.. 9: [ . 1 2 3 2 ] 4 1111..1... 10: [ . 1 2 3 3 ] 4 1111.1.... 11: [ . 1 2 3 4 ] 4 11111..... 12: [ . 1 2 2 1 ] 4 111.1..1.. 13: [ . 1 2 2 2 ] 4 111.1.1... 14: [ . 1 2 2 3 ] 4 111.11.... 15: [ . 1 2 1 1 ] 4 111..1.1.. 16: [ . 1 2 1 2 ] 4 111..11... 17: [ . 1 2 . 1 ] 4 111...11.. 18: [ . 1 1 1 . ] 3 11.1.1..1. 19: [ . 1 1 2 . ] 3 11.11...1. 20: [ . 1 1 2 1 ] 4 11.11..1.. 21: [ . 1 1 2 2 ] 4 11.11.1... 22: [ . 1 1 2 3 ] 4 11.111.... 23: [ . 1 1 1 1 ] 4 11.1.1.1.. 24: [ . 1 1 1 2 ] 4 11.1.11... 25: [ . 1 1 . 1 ] 4 11.1..11.. 26: [ . 1 . 1 . ] 3 11..11..1. 27: [ . 1 . 1 1 ] 4 11..11.1.. 28: [ . 1 . 1 2 ] 4 11..111... 29: [ . 1 . . 1 ] 4 11..1.11.. 30: [ . . 1 . . ] 2 1.11..1.1. 31: [ . . 1 1 . ] 3 1.11.1..1. 32: [ . . 1 2 . ] 3 1.111...1. 33: [ . . 1 2 1 ] 4 1.111..1.. 34: [ . . 1 2 2 ] 4 1.111.1... 35: [ . . 1 2 3 ] 4 1.1111.... 36: [ . . 1 1 1 ] 4 1.11.1.1.. 37: [ . . 1 1 2 ] 4 1.11.11... 38: [ . . 1 . 1 ] 4 1.11..11.. 39: [ . . . 1 . ] 3 1.1.11..1. 40: [ . . . 1 1 ] 4 1.1.11.1.. 41: [ . . . 1 2 ] 4 1.1.111... 42: [ . . . . 1 ] 4 1.1.1.11..
Right column gives parens: "1" and "." for "(" and ")". Each update costs less than 10 CPU cycles.
Here is lex order, paren-lex-demo.cc, using paren-lex.h: 1: ((((())))) 11111..... [ . 1 2 3 4 ] [ . 1 2 3 4 ] 0 2: (((()()))) 1111.1.... [ . 1 2 3 3 ] [ . 1 2 3 5 ] 4 3: (((())())) 1111..1... [ . 1 2 3 2 ] [ . 1 2 3 6 ] 4 4: (((()))()) 1111...1.. [ . 1 2 3 1 ] [ . 1 2 3 7 ] 4 5: (((())))() 1111....1. [ . 1 2 3 . ] [ . 1 2 3 8 ] 4 6: ((()(()))) 111.11.... [ . 1 2 2 3 ] [ . 1 2 4 5 ] 3 7: ((()()())) 111.1.1... [ . 1 2 2 2 ] [ . 1 2 4 6 ] 4 8: ((()())()) 111.1..1.. [ . 1 2 2 1 ] [ . 1 2 4 7 ] 4 9: ((()()))() 111.1...1. [ . 1 2 2 . ] [ . 1 2 4 8 ] 4 10: ((())(())) 111..11... [ . 1 2 1 2 ] [ . 1 2 5 6 ] 3 11: ((())()()) 111..1.1.. [ . 1 2 1 1 ] [ . 1 2 5 7 ] 4 12: ((())())() 111..1..1. [ . 1 2 1 . ] [ . 1 2 5 8 ] 4 13: ((()))(()) 111...11.. [ . 1 2 . 1 ] [ . 1 2 6 7 ] 3 14: ((()))()() 111...1.1. [ . 1 2 . . ] [ . 1 2 6 8 ] 4 15: (()((()))) 11.111.... [ . 1 1 2 3 ] [ . 1 3 4 5 ] 2 16: (()(()())) 11.11.1... [ . 1 1 2 2 ] [ . 1 3 4 6 ] 4 17: (()(())()) 11.11..1.. [ . 1 1 2 1 ] [ . 1 3 4 7 ] 4 18: (()(()))() 11.11...1. [ . 1 1 2 . ] [ . 1 3 4 8 ] 4 19: (()()(())) 11.1.11... [ . 1 1 1 2 ] [ . 1 3 5 6 ] 3 20: (()()()()) 11.1.1.1.. [ . 1 1 1 1 ] [ . 1 3 5 7 ] 4 21: (()()())() 11.1.1..1. [ . 1 1 1 . ] [ . 1 3 5 8 ] 4 22: (()())(()) 11.1..11.. [ . 1 1 . 1 ] [ . 1 3 6 7 ] 3 23: (()())()() 11.1..1.1. [ . 1 1 . . ] [ . 1 3 6 8 ] 4 24: (())((())) 11..111... [ . 1 . 1 2 ] [ . 1 4 5 6 ] 2 25: (())(()()) 11..11.1.. [ . 1 . 1 1 ] [ . 1 4 5 7 ] 4 26: (())(())() 11..11..1. [ . 1 . 1 . ] [ . 1 4 5 8 ] 4 27: (())()(()) 11..1.11.. [ . 1 . . 1 ] [ . 1 4 6 7 ] 3 28: (())()()() 11..1.1.1. [ . 1 . . . ] [ . 1 4 6 8 ] 4 29: ()(((()))) 1.1111.... [ . . 1 2 3 ] [ . 2 3 4 5 ] 1 30: ()((()())) 1.111.1... [ . . 1 2 2 ] [ . 2 3 4 6 ] 4 31: ()((())()) 1.111..1.. [ . . 1 2 1 ] [ . 2 3 4 7 ] 4 32: ()((()))() 1.111...1. [ . . 1 2 . ] [ . 2 3 4 8 ] 4 33: ()(()(())) 1.11.11... [ . . 1 1 2 ] [ . 2 3 5 6 ] 3 34: ()(()()()) 1.11.1.1.. [ . . 1 1 1 ] [ . 2 3 5 7 ] 4 35: ()(()())() 1.11.1..1. [ . . 1 1 . ] [ . 2 3 5 8 ] 4 36: ()(())(()) 1.11..11.. [ . . 1 . 1 ] [ . 2 3 6 7 ] 3 37: ()(())()() 1.11..1.1. [ . . 1 . . ] [ . 2 3 6 8 ] 4 38: ()()((())) 1.1.111... [ . . . 1 2 ] [ . 2 4 5 6 ] 2 39: ()()(()()) 1.1.11.1.. [ . . . 1 1 ] [ . 2 4 5 7 ] 4 40: ()()(())() 1.1.11..1. [ . . . 1 . ] [ . 2 4 5 8 ] 4 41: ()()()(()) 1.1.1.11.. [ . . . . 1 ] [ . 2 4 6 7 ] 3 42: ()()()()() 1.1.1.1.1. [ . . . . . ] [ . 2 4 6 8 ] 4
Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Speaking of lexicography, the semifinal rounds of the (U.S.) National Spelling Bee are currently broadcasting on cable channel ESPN2. The finals will start in about 4 hours from now. --Dan On 2013-05-30, at 1:05 PM, Fred lunnon wrote:
Having completed my exhausting survey of the competition for a lexicographic generator, I award myself a gallant third place (out of three) for elegance, and a narrow first for usability. Ruskey <BinTreeLex.c> and Arndt <paren-lex.h>
Apologies: Ruskey's <binGray.c> malfunctioned for small n , _not_ <BinTreeLex.c> as earlier claimed. That will teach me not to snigger --- or maybe it won't, since not for the first time ... [Exit laughing on other side of face, as my parents would quaintly have put it.] WFL On 5/30/13, Fred lunnon <fred.lunnon@gmail.com> wrote:
Having completed my exhausting survey of the competition for a lexicographic generator, I award myself a gallant third place (out of three) for elegance, and a narrow first for usability. Ruskey <BinTreeLex.c> and Arndt <paren-lex.h> both eschew recursion, and Arndt's very clean algorithm is somewhat shorter. However, he represents a bracketing only as a sequence of locations of left brackets: including updating the string itself would leave all three efforts approximately the same length. Ruskey falls over on special cases n = 1,2 --- hee-hee, who tested that program then?
As to single transposition "Gray-code" generators, Ruskey <algorithm 5.16, binGray.c> provides an instructive pair of mutually recursive procedures which seem to work --- more than I can manage at the moment --- but which would be a nightmare to adapt to the co-routine / object-oriented model required by a large-scale modular application --- where the user needs to pull up the "next" thingy on demand, as opposed to building a bloat-load of the complete set beforehand.
Arndt <paren-gray.h> does everything right (apart from actually telling the user how a bracketing is represented), quoting a reference Tadao Takaoka, Stephen Violich "Combinatorial Generation by Fusing Loopless Algorithms" which should repay further investigation.
I'm motivated to reflect on the sad fact that recursion and co-routines are incompatible paradigms. Furthermore, while it is undoubtedly harder initially to write "loopless" (yerwot?) algorithms, they do seem in practice noticeably easier to debug than their recursive counterparts.
Fred Lunnon
participants (6)
-
Dan Asimov -
Fred lunnon -
Joerg Arndt -
Mike Stay -
Victor Miller -
Wouter Meeussen