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.
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  
 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 filling-in 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 C-influenced-language 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 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 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 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

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



Sun, 11 Jul 2004 07:28:07 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. identity = lambda x: x -- a Pythonic idiom?

2. pythonic tree-walking idioms

3. Pythonic way of web-programming

4. A few idioms and programs for new J'ers

5. Smalltalk programming idioms and styles

6. Programming Idiom

7. Smalltalk programming idioms and styles

8. Programming language as a puzzle

9. Programming language as a puzzle

10. Another Silly programming puzzle....

11. Programming Puzzle! (assembly)

12. Programming Puzzle! (assembly)

 

 
Powered by phpBB® Forum Software