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