A puzzle for Pythonistas

[Anton Vredegoor]

On Thu, 6 Feb 2003 03:07:44 +0000 (UTC), mlh at furu.idi.ntnu.no (Magnus
Lie Hetland) wrote:

>Although you have already received several answers, I can't resist
>writing up a solution to this one... The code below creates all

Sometimes the obvious solution is overlooked ... I am glad you posted
it!

>subsets -- filtering out those of length 0 and 1 would, of course, be
>trivial (and less general). Also, I'm using the compress() function
>from numarray. Feel free to replace compress(cond, x) with a list
>comprehension such as [x[i] for i in range(n) if cond[i]] if you don't
>want to use numarray (or have numeric arrays returned).
>
>from numarray import compress
>def subsets(seq):
>    n = len(seq)
>    for i in xrange(2**n):
>        cond = [bool(2<<j & i) for j in xrange(n)]
>        yield compress(cond, seq)

There are a few problems with this code, although I grant it must have
been written by someone who saw the answer.

a) the test should be 1<<j & i
b) using compress this way causes a traceback?

After some refactoring:

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

def test():
    L=list("abcd")
    for i in range(2**(len(L))):
        print subset(L,i)

if __name__=='__main__':
    test()

Now if someone could re-arrange the integers in a range so that the #
of bits that are set increases monotonically this would be even better
:-)

Regards,
	Anton