* 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