Re: [math-fun] Subset-lex: did we miss an order?
I scratched my head over this, but now I think these "iterators" must be the same thing as loopless generators --- see http://en.wikipedia.org/wiki/Loopless_algorithm This topic has surfaced previously on math-fun, with respect to various combinatorial problems; two insights have arisen during my investigations. Firstly, that a decent object-oriented / ADT programming environment greatly facilitates the implementation and useability of such tools. Secondly, recursion -- hoary standby of so many programming courses -- and looplessness seem mutually incompatible. Converting one type of algorithm into the other is a process which somehow should be mechanical, but in practice always proves next to impossible in nontrivial situations. Fred Lunnon On 6/10/14, Joerg Arndt <arndt@jjj.de> wrote:
I missed this message...
I agree that a project "iterators" as suggested below appears worthwhile. The chances of adoption in other programs (say, Sage) appear low, however.
This is way I concentrate an finding new orders with interesting properties instead. "interesting properties" would be "changes only at end and of bounded length" for these subset-lex and SL-Gray orders.
It seems hard to believe that the Gray code for compositions isn't already known; I tried hard to find it in the literature, to no avail.
Best regards, jj
* rcs@xmission.com <rcs@xmission.com> [May 28. 2014 12:13]:
Once upon a time, I worked at a Lisp-based company. The main technical guru had built a package of "iterators" that fit into the Lisp loop sub-language. Simple iterators were to count through a range, to march down a list or array, and to run through special sets relevant to the company.
I later wrote a long list of iterator-combiners that would take cross-products of iterations in various orders, and handle instructions like "next", and perhaps "previous", "skip to next row", "goto position N", and so on. I never wrote any actual code.
I think this might be a worthwhile activity, at least as an intellectual exercise.
Rich
On Tue, Jun 10, 2014 at 10:37 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Secondly, recursion -- hoary standby of so many programming courses -- and looplessness seem mutually incompatible. Converting one type of algorithm into the other is a process which somehow should be mechanical, but in practice always proves next to impossible in nontrivial situations.
Do you have any evidence for this assertion? Scheme compilers seem to work, and they are required by the language spec to convert certain sorts of recursive programs to iterative ones. I program professionally in Lisp, currently using the Lispworks compiler, and it successfully transforms recursive procedures to iterative ones. Andy
Apologies for muddying the waters here. Now I've done some homework, I see that the emphasis is syntactic rather than algorithmic. Iterators and containers: see http://en.wikipedia.org/wiki/Iterator Andy Latto:
Do you have any evidence for this assertion? Scheme compilers seem to work, and they are required by the language spec to convert certain sorts of recursive programs to iterative ones.
Is this "tail-call optimization" ? http://en.wikipedia.org/wiki/Scheme_%28programming_language%29 I'll wriggle here and admit that I don't any more properly recall how this problem relates to the sort of combinatorial algorithms Joerg and I have in mind. My only scrap of evidence is that I can't (always) manage to do it --- as implied earlier, I'm not claiming that it's impossible at all --- I feel the process ought to be mechanical, but in practice don't see how. A good example of what I mean is algorithm 5.16 in Frank Ruskey's "Combinatorial Generation" for recursive generation of adjacent bracketings. http://www.1stworks.com/ref/RuskeyCombGen.pdf I have stared at this for a goodly while trying to figure out how to transform it into a "loopless" algorithm --- replacing the recursion by backtracking so as to deliver each new bracketing in CAT given the previous one --- but have so far had to admit defeat. Fred Lunnon On 6/10/14, Andy Latto <andy.latto@pobox.com> wrote:
On Tue, Jun 10, 2014 at 10:37 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Secondly, recursion -- hoary standby of so many programming courses -- and looplessness seem mutually incompatible. Converting one type of algorithm into the other is a process which somehow should be mechanical, but in practice always proves next to impossible in nontrivial situations.
Do you have any evidence for this assertion? Scheme compilers seem to work, and they are required by the language spec to convert certain sorts of recursive programs to iterative ones. I program professionally in Lisp, currently using the Lispworks compiler, and it successfully transforms recursive procedures to iterative ones.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Fred Lunnon <fred.lunnon@gmail.com> [Jun 10. 2014 18:10]:
I scratched my head over this, but now I think these "iterators" must be the same thing as loopless generators --- see http://en.wikipedia.org/wiki/Loopless_algorithm This topic has surfaced previously on math-fun, with respect to various combinatorial problems; two insights have arisen during my investigations.
Firstly, that a decent object-oriented / ADT programming environment greatly facilitates the implementation and useability of such tools.
Secondly, recursion -- hoary standby of so many programming courses -- and looplessness seem mutually incompatible. Converting one type of algorithm into the other is a process which somehow should be mechanical, but in practice always proves next to impossible in nontrivial situations.
If you have a recursive routine that would be loopless, the cascade of returns when a stack of calls is just at end implies a "loop". If there'd be an instruction "call next level with return address of caller of this level" then you'd be there. Now read up on the BER trick (in TAOCP and/or) the two(?) original papers, and you'll see. I wish that explanation would have been given in TAOCOP (or _anywhere_ else)! One particularly (IMO) nice feature of the subset-lex orders is that they are (often) loopless without O(n) extra storage (BER trick, Knuth calls the array "focus" pointers), not even O(1) extra storage is needed, but O(0), that is, none. Best, jj
Fred Lunnon
[...]
participants (3)
-
Andy Latto -
Fred Lunnon -
Joerg Arndt