Two Ruby Versions

Post #121,741 by JimWeirich 10/17/03 5:23:19 PM Reply	Two Ruby Versions First, the Ruby version of Scott's Python one-liner ... `puts "BCB".unpack("C*").map{\|b\| "A"..b.chr}.inject{\|a,b\| a.map{\|x\| b.map{\|y\| x+y}}.flatten}` It is essentially the same algorithm, with the following notes: "reduce" is spelled "inject" in Ruby (version 1.8 or later) The Ruby version reads left to right, instead of inside out like the Python version. Ruby strings iterate on lines rather than chars, so I used unpack to get an array of character ordinals (and converted back to strings using .chr) The nested maps in the injection block returns a nested list, so I used flatten on the result before giving it back to inject. Ruby's glob doesn't work in the same way as Perl's (AFAIK) so a Ruby version of the Perl one-liner would be difficult. (BTW, cool use of glob!) Although the one liners are cool, its not how I would have approached it. After several false starts, I came up with the following function that I find quite straight forward. I'm interested in other opinions. def all_combinations(letters, prefix="", &block)\n if letters.length == 0\n yield prefix\n else\n ("A"..letters[0..0]).each do \|letter\|\n all_combinations(letters[1..-1], prefix + letter, &block)\n end\n end\n end\n\n all_combinations("BCB") { \|str\| puts str }\n The guts of the function is in the else clause where we create a range ('A'..letters[0..0]) of all the possible first letters and recursively combine that with the combinations based on the tail (letters[1..-1]) of the string. The `if` condition terminates the recursion when there are no more letters left and yields up the prefix string for that combination. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
Post #121,743 by admin 10/17/03 5:30:56 PM Reply	Recursive + stack space... One of Bryce's requirements was that a recursive algorithm not be used, in order to allow for the iteration of very large character spaces. Honestly, though, I typically find recursive algorithms to be more opaque to quick understanding than iterative algorithms. This probably has something to do with my dislike of LISP. ;-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,747 by JimWeirich 10/17/03 6:31:32 PM Reply	Re: Recursive + stack space... One of Bryce's requirements was that a recursive algorithm not be used Actually, the statement was "rather not try recursion because the stack could get too deep". In this algorithm, the recursion depth is bounded by the length of the string, so stack depth is not a problem. (The example string only needs a stack depth of 4). Regarding the understanding of recursive algorithms, I can't help you there. I often find the opposite to be true. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
Post #121,832 by admin 10/18/03 1:15:01 PM Reply	Ah, ok. See what I mean about finding recursion opaque? :-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,834 by deSitter 10/18/03 1:28:31 PM Reply	Proof by induction Ever formally been through this? Say one has a proposition that depends on an integer. 1) Let the proposition be manifestly true for K=1. 2) Assume the proposition is true for K. If 1) and 2) imply that the proposition is true for K+1, then it's true for any K. Example: Proposition: 1+2+...+N = 1/2(N+1)N 1) Clearly true for N=1. 2) Assume 1+2+...+(N-1) = 1/2N(N-1). Then 1+2+...+(N-1)+N = 1/2N(N-1) + N = N(1/2(N-1) + 1) = 1/2N(N+1) So it's true for any N. That's basically all there is to recursion. -drl
Post #121,836 by admin 10/18/03 1:32:39 PM Reply	... I have a degree in algorithmic mathematics. Of course I've been through proof by induction. :-) I know how recursion works, and I can figure it out. However, it doesn't come instantly to understanding. While the same thing might be said for functional programming, I don't have as much of an issue with it for some reason. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,839 by deSitter 10/18/03 1:49:38 PM Reply	(sheepish grimace) Yes, recursion is trivial in APL, the prototype for a functional language. -drl
Post #121,842 by JimWeirich 10/18/03 2:51:28 PM Reply	Recursion and Lisp I had Daniel Friedman (author of the Little Lisper) as a first year CS instructor in college. The class was supposed to be an introduction to FORTRAN (that dates me!). But when I went to class, Prof. Friedman kept writing code on the board that had way too many parenthesis for FORTRAN. I spent about three days in class absolutely confused and lost. Around the third day understanding dawned and recursion (and LISP) started making a lot of sense. Its a powerfull tool to have on your workbench. If you ever come across a copy of the Little Lisper (or Little Schemer), its a fairly gentle way to become comfortable with recursion (and a lot of other ideas). The books are written in a style that's not too different from the way Friedman teaches. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
Post #121,845 by admin 10/18/03 3:31:03 PM Reply	You still misunderstand me. I'm perfectly comfortable reading and writing recursive code. I just don't find it the easiest code for immediate understanding. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,853 by deSitter 10/18/03 8:05:14 PM Reply	Re: You still misunderstand me. Well, I think it probably is psychologically harder, because in the back of your mind you're worrying about the recursion converging. -drl
Post #121,850 by FuManChu 10/18/03 5:34:05 PM Reply	Only other people's... :) I find it very natural, understandable, and quick to write them; reading one created by someone else is another story; it takes a certain amount or style of documentation to make it easier. This probably has something to do with my dislike of LISP. ;-) Been following the world-record-for-crossposting thread on comp.lang.python + comp.lang.lisp? "Python syntax in Lisp and Scheme" and now "Why don't people like lisp?" Entertaining stuff. "There's a set of rules that anything that was in the world when you were born is normal and natural. Anything invented between when you were 15 and 35 is new and revolutionary and exciting, and you'll probably get a career in it. Anything invented after you're 35 is against the natural order of things." Douglas Adams
Post #121,858 by admin 10/18/03 9:20:21 PM Reply	No, I should go look that one up. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,745 by ben_tilly 10/17/03 6:18:01 PM Reply	Let me golf the one-liner a little... `ruby -e'p"BCB".split(//).map{\|b\|"A"..b}.inject{\|a,b\|a.map{\|x\|b.map{\|y\|x+y}}.flatten}'` Mostly this was just removing unneeded spaces. I also switched puts to p, (changes the output, but Scott had already changed the output so I thought that fair), and used split rather than an unpack. And for those who haven't bothered to understand the algorithm, here is a commented version of the one-liner. \nputs \\\n "BCB".split( # Take the string and split it\n // # on the spaces between strings\n ).map{\|b\| # foreach character b that you get\n "A"..b # make an array "A"..b\n }.inject{\|a,b\| # foreach of those arrays, let a be the partial\n # answer so far and b be next array (the\n # first array is the first partial answer)\n a.map{\|x\| # each x in a turns into\n b.map{\|y\| # an array of turning each y in b into\n x+y # concatenate x and y\n } \n }.flatten # and then flatten the array of arrays into a\n # single-level array of strings\n } # the last partial answer is our full one\n BTW it may be me, but I find the Ruby version much more readable than the Python. My guess is that I am reacting to the fact that all of the logic is naturally reading left to right, top to bottom. Cheers, Ben "good ideas and bad code build communities, the other three combinations do not" - [link\|http://archives.real-time.com/pipermail/cocoon-devel/2000-October/003023.html\|Stefano Mazzocchi]
Post #121,748 by JimWeirich 10/17/03 6:48:44 PM Reply	Ooo ... Good call on split And split returns single character strings rather than integers so ".chr" is not needed. You could also use scan(/./), but it would be the same golf score. Just a minor nit-pick on the comments ).map{\|b\| # foreach character b that you get\n "A"..b # make an array "A"..b Should be "make a range from "A" to b. A range object doesn't store every element of the range, but only the first and last elements, so ("A".."B") takes the same amount of storage as ("A".."Z"). Which makes the call to inject interesting. The first time inject invokes its block, a range object is passed as parameter a. The remaining times the flattened array from the previous invocation is passed. Since map works on both arrays and ranges, we don't care. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

Welcome to IWETHEY!