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