Pythonic idioms / Programming Puzzle

[Alex Martelli]

ameoba wrote:
        ...
> 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.

> 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.


> 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.:

>     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