SICP subsets exercise in python?

[Alex Martelli]

"Brian Zhou" <brian_zhou at agilentNOSPAM.com> wrote in message
news:980725379.806449 at emperor.labs.agilent.com...
> Just curious if I can do it easily in Python, kind of give up after a few
> tries. Anyone?
>
> /Brian
>
>
> Exercise. We can represent a set as a list of distinct elements, and we
can
> represent the set of all subsets of the set as a list of lists. For
example,
> if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3)
(1)
> (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure
that

In Python, one would normally operate iteratively, just as in Scheme one
normally operates with tail recursion (the power is the same, but the
two different approaches are appropriate to the two languages).

There is an obvious isomorphism between the set of subsets of a list L of
length N, and the set of binary numbers between 0 and (2**N)-1 -- map
each element of L to its index, and have each subset S correspond to the
number X for which bits are set to 1 for the indices of elements of L
that are in S.

It's simpler to express this in Python of course...!-).

def subsetOfX(L, X):
    S = []
    for i in range(len(L)):
        if X&(2L**i):
            S.append(L[i])
    return S

or, more concisely but equivalently:

def subsetOfX(L, X):
    return [L[i] for i in range(len(L))
        if X & (1L<<i)]

So, the set-of-all-subsets:

def setOfSubsets(L):
    return [subsetOfX(L, X)
        for X in range(2**len(L))]

We don't NEED the auxiliary function
subsetOfX of course, if we prefer...:

def setOfSubsets(L):
    N = len(L)
    return [ [ L[i] for i in range(N)
                if X & (1L<<i) ]
        for X in range(2**N) ]


Alex