Ick. Globals.

Post #121,438 by admin 10/16/03 11:12:49 AM Reply	Ick. Globals. The globals actually detract from the readability of yours, IMO. I had to read it through a few times before I caught that part. Nasty. :-P Also note that since yours is recursive, it might have stack issues for large limit strings. The rilly rilly readable version of mine: \n"""\nEnumerate a string.\n\nFirst the string is turned into an array of single character strings.\n\nEach column is then incremented until it overflows as compared to a maximum\nstring. At overflow, the column is reset to A and the next column is incremented.\nWhen the last column has overflowed, the string enumeration is complete.\n\nEssentially, the string is treated as a number where each column has a different\nbase. :-)\n"""\n\n# Increment a string array.\ndef incStringArray(stringArray, maxString):\n # increment the 1st column\n stringArray[0] = stringArray[0] + 1\n\n lastColumn = len(stringArray) - 1\n\n # check each column to see if it needs to be rolled\n for column in range(0, lastColumn + 1):\n \n # check to see if the current column needs to be rolled\n if stringArray[column] > maxString[column]:\n # we're at the end and done; overflow\n if column == lastColumn: return None\n\n # reset the column to the beginning\n stringArray[column] = ord('A')\n\n # increment the next column\n nextColumn = column + 1\n stringArray[nextColumn] = stringArray[nextColumn] + 1\n\n return stringArray\n\n\ndef enumerateString(stringToEnumerate):\n # turn the string into ordinals (character array)\n stringArray = map(ord, stringToEnumerate)\n\n # set up a seed ordinal array to increment\n currentEnum = map(ord, list('A' * len(stringArray)))\n\n while currentEnum:\n # return the string array mapped back to character values from ordinals\n yield ''.join(map(chr, currentEnum))\n currentEnum = incStringArray(currentEnum, stringArray)\n\n\nfor string in enumerateString('BDC'):\n print string\n I went back to the generator to enable the algorithm to be used as an easy iterator. Also, there are two usable routines: increment a string array, and generate a list of strings. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,487 by FuManChu 10/16/03 3:32:18 PM Reply	Granted. That's the first time I've ever use the "global" keyword. Ever. I feel dirty. :D I would usually package that up in a class or something. I also briefly toyed with the idea of working in the opposite direction, so that one would restart inner loops when 'A' was reached descending, rather than ascending to the limit of each column. That might reduce some of the argument passing. But I had other things to do. I also toyed with one-liners for a while, starting with the following: \n>>> word = 'BCB'\n>>> [[y for y in range(ord(x) - 64)] for x in word]\n[[0, 1], [0, 1, 2], [0, 1]] My thought was to then iterate successively over each sequence in turn, combining reduce() and list comprehensions somehow, but I really don't have that much time. :D Oh, and ick. One comment per line. Nasty. :P "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,505 by admin 10/16/03 4:32:00 PM Reply	Like this? `print reduce(lambda a, b: [x + y for x in a for y in b], [[chr(y) for y in range(ord('A'), ord(x) + 1)] for x in 'BCB'])` Muahahaha. What's that you say? TIMTOWTDI? cackle WRT comments, you can't please everyone. ;-) Or, the more "readable" version (all one line, not using <pre> so it doesn't make browser windows too wide): `print reduce(lambda firstList, secondList: [firstFragment + secondFragment for firstFragment in firstList for secondFragment in secondList], [[chr(rangeLetter) for rangeLetter in range(ord('A'), ord(letter) + 1)] for letter in 'BCB'])` Hee hee hee. Fun, ain't it? ;-) I love Python. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,510 by admin 10/16/03 5:02:10 PM Reply	This is probably worth decomposing, too I thought it worthwhile to decompose the one-liner, just to show what is actually happening behind the scenes. Thus we see the power of CHEESE! Er, functional programming, that is... \nword = "AGB"\n\n# get a list of lists of the ranges represented by the word\ncharRange = []\nfor c in word:\n charList = []\n # The ord is necessary because range requires integers\n for x in range(ord('A'), ord(c) + 1):\n charList = charList + [chr(x)]\n\n print "Range for character %s: " % c, charList\n \n charRange = charRange + [charList]\n \nprint "List of ranges for individual characters: ", charRange\n\n# go through each range of characters and append each one to each character in the\n# next range of characters. This emulates the 'reduce' portion.\nresults = charRange[0]\nfor curRange in range(1, len(charRange)):\n cur = []\n for x in results:\n for y in charRange[curRange]:\n cur = cur + [x + y]\n results = cur\n print "Interim results: ", results\n \nprint "Final results: " , results\n Output: Range for character A: ['A'] Range for character G: ['A', 'B', 'C', 'D', 'E', 'F', 'G'] Range for character B: ['A', 'B'] List of ranges for individual characters: [['A'], ['A', 'B', 'C', 'D', 'E', 'F', 'G'], ['A', 'B']] Interim results: ['AA', 'AB', 'AC', 'AD', 'AE', 'AF', 'AG'] Interim results: ['AAA', 'AAB', 'ABA', 'ABB', 'ACA', 'ACB', 'ADA', 'ADB', 'AEA', 'AEB', 'AFA', 'AFB', 'AGA', 'AGB'] Final results: ['AAA', 'AAB', 'ABA', 'ABB', 'ACA', 'ACB', 'ADA', 'ADB', 'AEA', 'AEB', 'AFA', 'AFB', 'AGA', 'AGB'] Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,523 by ben_tilly 10/16/03 7:10:58 PM 10/16/03 7:31:28 PM Reply	Now you've EARNED my nasty Perl tricks... `perl -e'$"=",";print"$_\\n"for glob join"",map"{@{[A..$_]}}",BCB=~/./g'` 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] Edited by ben_tilly Oct. 16, 2003, 07:12:25 PM EDT Edited by ben_tilly Oct. 16, 2003, 07:31:28 PM EDT Expand All History
Post #121,530 by admin 10/16/03 7:29:32 PM Reply	Yabut... People can actually understand the Python one-liner. ;-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,535 by deSitter 10/16/03 7:56:41 PM Reply	Re: Yabut... The APL idiom is pretty simple, despite appearences - the -64 and 65 are for creating an "index vector" 1 2 3...n starting at A and ending at whatever letter represented by n - taken from the "atomic vector" []av which is a system variable representing the collating sequence. Once you simplify that it's just @@(i"0 (-1+i SEQ i 'DATA'))@SEQ where SEQ is the subset "@A...Z" of the atomic vector. So this idiom 1) Creates an array with a number of rows = the number of letters in DATA, where each row is 1 2 3...L(n), L(n) being the nth letter in DATA. 2) Indexes that array into SEQ to produce the corresponding array of letters 3) "Unrolls" this enclosed array twice to produce the various permutations. The selection operator "from" is thus used three times, once dyadically and twice monadically. The indexing operator "index" (i) is also used once dyadically and twice monadically (not an accident, the operators are complementary). The "rank" operator allows the "index" operator to go inside the argument array by explicitly modifying the expected strucutre of the argument - this is a very powerful APL feature that is like a "view" on an array, that is, "for this case, this isn't an MxN matrix of scalars, it's M vectors of length N", etc. etc. This is how APL programming works - one writes statements that exhibit algorithms. -drl
Post #121,537 by FuManChu 10/16/03 8:00:38 PM Reply	Appearances are complexity Your description only makes it simpler if one understands the terms "index vector", "atomic vector", "collating sequence", "array" as a verb, "unrolls", "dyadically" and "monadically", and "operator". ;) "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,536 by ben_tilly 10/16/03 7:58:47 PM Reply	They can? Were you so confident of that, I doubt that you would have deconstructed your code to try to explain it... 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,538 by deSitter 10/16/03 8:04:07 PM Reply	Ruby? (Perl was impressive, knock me out dude) -drl
Post #121,539 by ben_tilly 10/16/03 8:11:02 PM Reply	Sorry, I am rusty enough not to attempt it But Scott's example should translate pretty directly after you implement reduce in Ruby. 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,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)
Post #121,542 by admin 10/16/03 8:26:45 PM Reply	Wrong interpretation. I deconstructed the example to show how powerful each of the functional, er, functions are, not to describe it better. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,532 by broomberg 10/16/03 7:37:25 PM Reply	Please deconstruct it for me I'm brain farting.
Post #121,534 by ben_tilly 10/16/03 7:56:38 PM Reply	Deconstructed If you understand what this does: `echo {A,B}{A,B,C}{A,B}` then you shouldn't be surprised at `perl -e'print"$_\\n"for glob"{A,B}{A,B,C}{A,B}"'` The key is therefore how to produce that string. Well we do it as: `perl -e'print"$_\\n"for glob join"","{A,B}","{A,B,C}","{A,B}"'` Now we just need to produce those. Well our first trick is $" and array interpolation. If you set $" to ",", then a list interpolates into a string with comma separators. So with that global set, `"@{[A..C]}"` is `"A,B,C"`. Slap braces around that, and you see what `"{@{[A..$_]}}"` does. Now we just need to get the right list of characters. `BCB=~/./g` does that in list context, which we are in. (I didn't think of that trick at first. My initial versions in the revision history used split.) And that's it. Cheers, Ben PS You will note that I am making liberal use of unquoted barewords as strings. This wouldn't exactly pass strict, but I don't have that on so I don't care. "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,692 by broomberg 10/17/03 1:55:58 PM Reply	Ahh I'm religiously opposed to glob so it didn't click! Maynow, as an internal, it is safe. But I always got burned on "command line too long" from globs so I always opendir, grep for what I want, close dir.
Post #121,694 by ben_tilly 10/17/03 2:01:30 PM Reply	Ditto, but I remember the stupid trick for golf "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,533 by FuManChu 10/16/03 7:56:33 PM Reply	Mein Gott. I learn something new and cool every day about Python. I had no idea about the construct: `for x in a for y in b` Thanks! "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,543 by admin 10/16/03 8:28:10 PM Reply	Yep. It's a great language. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."

Welcome to IWETHEY!