Pythonic idioms / Programming Puzzle
Author 
Message 
ameob #1 / 5

Pythonic idioms / Programming Puzzle
The other day, I got caught up in nostalgia, and decided to look around at some LOGO (y'know, turtle graphics &C) webzits. What to my wondering eyes should appear but an acknowledgement that LOGO is a variant of LISP and  not just a toy language. To prove it there was an example program ( http://www.***.com/ ~bh/logosample.html ) that printed permutations of an arbitrary list of arbitrarily long lists of strings. in 4 lines. Python's a new thing for me, so in my newborn zeal, I decided to show that python could do it just as well, using lists defined like:  list = [["Small","Medium","Large"], ["Mountain Dew", "root beer", "orange juice"], ["\b, a"], ["hamburger", "cheeseburger", "double cheeseburger"], ["\b, and a"], ["small", "medium", "large"], ["fries."]]  So I essentially translated it to Python, which resulted in this:  #recursive arbitrary list of lists permuter. def choices(menu, sofar = ""): if(menu == []) : print sofar.strip() else : for x in menu[0] : choices(menu[1:],sofar+" "+x)  Which was fine and dandy, but I couldn't stop with simply translating somebody elses work. I wanted to come up with an iterative solution, which gave me :  # arbitrary list of lists permuter. Iterative version. # Esentially a series of different base N counters # where N is determined by the length of the corresponding list # with overflows carried over to the next place def ichoices(menulist = []): #init counter counter = [0]*len(menulist) #loop 'till counter overruns on last element # (god I love reverse array indexing, sweet syntactic sugar) while counter[1] < len(menulist[1]): #build & print the combination t = "" for x in range(len(menulist)): t += " " + menulist[x][counter[x]] print t.strip() #increment counter, and handle overflows by carry to next place #except for the last place, since the overflow there #is our termination condition counter[0] += 1 for x in range(len(counter)1): if counter[x] >= len(menulist[x]): counter[x] = 0 counter[x+1] += 1  Which, at 12 lines of code, is longer but (perhaps just because I wrote it) a bit easier to follow. Looking at these two fundamentally different solutions to the same problem got me thinking... Obviously, both of these solutions are correct and fully functional, but is one a more Pythonic way of solving the problem, or is there an even more Pythonic solution floating arround? Another question; Does my code show that I have any perceptable 'accent'? That is to ask, am I obviously influenced by the other languages I've worked in (mostly C/Java/C++)?

Wed, 07 Jul 2004 21:51:51 GMT 


Alex Martell #2 / 5

Pythonic idioms / Programming Puzzle
... Quote: > permutations of an arbitrary list of arbitrarily long lists of strings.
Actually, I don't see where permutations enter the picture (every item stays in place  permutation is changing order), but I think I get what you mean (from your examples below)  given a list of lists, L, return the list of all lists, R, such that, for each list r in R, r[i] is an item from L[i] for each valid i. Quote: > Looking at these two fundamentally different solutions to the same problem > got me thinking... Obviously, both of these solutions are correct and > fully functional, but is one a more Pythonic way of solving the problem, > or is there an even more Pythonic solution floating arround?
I like your solutions, and I think the recursive one is more Pythonic since it's so much simpler, although I do personally prefer to consider such enumeration problems in terms of "counting in multiple bases", as you do in the second case. Here's what I consider a somewhat more Pythonic dressing for the recursive solution: def choices(menu, sofar = []): if menu: result = [] for x in menu[0]: result.extend(choices(menu[1:], sofar+[x])) return result else: return [" ".join(sofar)] Here's a traditional "recursion elimination" over this by introduction of an auxiliary stack: def choices(menu, sofar = []): result = [] stack = [] while 1: if menu: for x in menu[0]: stack.append((menu[1:], sofar+[x])) else: result.append(" ".join(sofar)) if stack: menu, sofar = stack.pop() else: break result.reverse() return result and here's a stranger approach, based on getting the resulting list's structure right off the bat and then fillingin its slots: def choices(menu): import operator totlen = reduce(operator.mul, map(len, menu)) result = [ menu[:] for j in range(totlen)] for i in range(len(menu)): j = 0 reps = totlen/len(menu[i]) while j < len(result): for item in menu[i]: for k in range(reps): result[j][i] = item j += 1 totlen = reps return map(" ".join, result) I think this latest is least Pythonic, being the most complex approach. Quote: > Another question; Does my code show that I have any perceptable 'accent'? > That is to ask, am I obviously influenced by the other languages I've > worked in (mostly C/Java/C++)?
Only marginally and superficially, in strange choice of parentheses and spaces, e.g.: Quote: > if(menu == []) : print sofar.strip()
I don't think the redundant parentheses after the if would occur to somebody without a Cinfluencedlanguage syntax's background; and most Pythonic would be to test menu directly (if menu or if not menu, rather than as you did if menu==[] or, as some other Cinfluenced programmers do, if len(menu) and so on). But this is little more than syntaxsugar anyway. The only somewhat substantial Pythonic instinct you're still lacking seems to be  don't build a string by repeated + or += (quite slow), rather put the pieces in a list (by append, extend, +, +=, or other ways yet) and when you're done ''.join it (or in this case ' '.join since we want separating spaces, apparently) back into a string. The performance difference gets so huge so fast that an experienced Pythonista always things in terms of the latter idiom. Alex

Thu, 08 Jul 2004 03:30:43 GMT 


Jason Orendorf #3 / 5

Pythonic idioms / Programming Puzzle
Quote:
> Obviously, both of these solutions are correct and > fully functional, but is one a more Pythonic way of solving the > problem, or is there an even more Pythonic solution floating > arround?
I'm rather fond of  def choices(menulist): def permute(L1, L2): return [a + ' ' + b for a in L1 for b in L2] for combo in reduce(permute, menulist, [""]): print combo  which is arguably iterative. As an interesting analog to your iterative rendering, the generators in Python 2.2 seem chiefly aimed at providing interesting new solutions to such puzzles. The advantage of using a generator is that it requires very little memory, since you can walk through the results without building a huge list of them. (Generators have proven pleasantly useless for almost every realworld task I have tried them with. :) Here I've separated the generation of the indexes from the string handling.  from __future__ import generators def genTuples(dims): N = len(dims) counters = [0] * N while 1: yield tuple(counters) # Increment the counters. for i in range(N): counters[i] += 1 if counters[i] >= dims[i]: counters[i] = 0 # Overflow to next index. else: break # No overflow; we're done. else: # Ran out of indices to increment. # This is our terminating condition. return def genChoices(menulist): from operator import getitem for indexTuple in genTuples(map(len, menulist)): yield " ".join(map(getitem, menulist, indexTuple)) for order in genChoices(my_menus): print order  Here is the recursive solution with a generator:  from __future__ import generators def genChoices2(menulist): if len(menulist) == 0: # Base case  one combination: the empty string. yield "" return first, rest = menulist[0], menulist[1:] for choice1 in first: for choice2 in gchoices(rest): yield choice1 + " " + choice2  ## Jason Orendorff http://www.jorendorff.com/

Thu, 08 Jul 2004 04:18:10 GMT 


Anton Vredego #4 / 5

Pythonic idioms / Programming Puzzle
Quote: >Looking at these two fundamentally different solutions to the same problem >got me thinking... Obviously, both of these solutions are correct and >fully functional, but is one a more Pythonic way of solving the problem, or >is there an even more Pythonic solution floating arround?
[Based also on parts of the code of the previous posters] This is the way I would do it: """ indexed menuchoice based on a list of a list of possible items """ from operator import mul class MenuChoice: def __init__(self,menulist): self.maxindex = reduce(mul,map(len, menulist))  1 self.menulist = menulist def __getitem__(self, index): res = [] counter = index if index > self.maxindex: raise IndexError, "No %ith menu avalable" else: for items in self.menulist: nitems = len(items) res.append(items[ counter % nitems]) counter /= nitems res.reverse return res def test(): menudata = [["Small","Medium","Large"], ["Mountain Dew", "root beer", "orange juice"], ["\b, a"], ["hamburger", "cheeseburger", "double cheeseburger"], ["\b, and a"], ["small", "medium", "large"], ["fries."]] menus = MenuChoice(menudata) for menu in menus: print " ".join(menu) if __name__=='__main__': test()

Thu, 08 Jul 2004 09:01:15 GMT 


Lloyd Goldwasse #5 / 5

Pythonic idioms / Programming Puzzle
Quote:
> [...] permutations of an arbitrary list of arbitrarily long lists of strings. > in 4 lines.
Here's a slightly different solution, one that puts the combinations* into lists rather than strings, which may have a wider applicability. It avoids explicitly building up a results string from [], at the expense of doing a length test: def choices(menulist): if len(menulist)>1: return [[x]+y for x in menulist[0] for y in choices(menulist[1:])] else: return [[x] for x in menulist[0]] and here's another one, not wildly different from Jason's stringoriented solution: def choices(menulist): return reduce(lambda L1,L2: [x+[y] for x in L1 for y in L2], menulist[1:], [[x] for x in menulist[0]]) (Both fail, though, if menulist is empty.) Lloyd * On a really pedantic note: "permutations" are changes in the order of a fixed set of elements (e.g., [a,b,c] > [[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]]). If I understand the question, we're talking "combinations" (taking one from list1, one from list2, and so on).  Lloyd Goldwasser Department of Demography
(510) 6420525 University of California fax: (510) 6438558 Berkeley, CA 947202120

Sun, 11 Jul 2004 07:28:07 GMT 


