help with code for combinations/permutations

[Alex Martelli]

"Andreas Jung" <andreas at andreas-jung.com> wrote in message
news:mailman.979764021.20668.python-list at python.org...
> On Wed, Jan 17, 2001 at 06:37:44PM +0000, Bryan Webb wrote:
> > Thanks to all that responded.
> >
> > I wasnt as clear as I should have been. (as usual)
> > I really need to come up with all the possible sums of the numbers in
the
> > list ie. 1 , sum(1 + 2), sum(1 + 2 + 3) ,sum( 1+2+4),sum( 1 + 3) and so
on.
>
> Ok, now you are talking about subsets but not of permutations. Because the
> order of the elements does not matter there are much fewer possibilities.
I

Specifically, a N-element set has 2**N subsets including the trivial ones.

> suggest to make an example by hand: take a set of 4 elements and generate
all
> subsets by hand. Then you will learn how such an algorithm should work.

Come on, it's much easier than that!

class Subsets:
    def __init__(self, alist):
        self.list=alist
    def __getitem__(self, n):
        L = len(self.list)
        if n>=(1<<L): raise IndexError,n
        return [self.list[i] for i in range(L) if n&(1<<i)]

and now just

    totals = {}
    for subset in Subsets(mylist):
        totals[reduce(operator.add,subset)]=1
    totals = totals.keys()
    totals.sort()
    print totals

or whatever subset-specific processing you desire.


Alex