Pythonic idioms / Programming Puzzle
Author Message
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/logo-sample.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.
if(menu == []) : print sofar.strip()
else :
----------

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
#init counter

#loop 'till counter overruns on last element
# (god I love reverse array indexing, sweet syntactic sugar)
#build & print the combination
t = ""
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):
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
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:

result = []
return result
else:
return [" ".join(sofar)]

Here's a traditional "recursion elimination" over this by introduction
of an auxiliary stack:

result = []
stack = []
while 1:
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 filling-in its slots:

import operator
result = [ menu[:] for j in range(totlen)]
j = 0
while j < len(result):
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 C-influenced-language syntax's background; and most Pythonic
did if menu==[] or, as some other C-influenced programmers do, if len(menu)
and so on).  But this is little more than syntax-sugar 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
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 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 real-world 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

from operator import getitem

print order
-------------

Here is the recursive solution with a generator:

-------------
from __future__ import generators

# Base case - one combination: the empty string.
yield ""
return
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
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

self.maxindex = reduce(mul,map(len, menulist)) - 1

def __getitem__(self, index):
res = []
counter = index
if index > self.maxindex:
raise IndexError, "No %ith menu avalable"
else:
nitems = len(items)
res.append(items[ counter % nitems])
counter /= nitems
res.reverse
return res

def test():
["Mountain Dew", "root beer", "orange juice"],
["\b, a"],
["hamburger", "cheeseburger", "double cheeseburger"],
["\b, and a"],
["small", "medium", "large"],
["fries."]]

if __name__=='__main__':
test()

Thu, 08 Jul 2004 09:01:15 GMT
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:

return [[x]+y for x in menulist[0] for y in
else:
return [[x] for x in menulist[0]]

and here's another one, not wildly different from Jason's
string-oriented solution:

return reduce(lambda L1,L2: [x+[y] for x in L1 for y in L2],

(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) 642-0525                                  University of California
fax: (510) 643-8558                             Berkeley, CA  94720-2120

Sun, 11 Jul 2004 07:28:07 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages