[Tutor] Re: recursion and power sets

[Thorsten Kampe]

* alice (2004-03-07 06:30 +0100)
> I was trying to write a function that would take a set - represented as a list 
> with non repeating elements - and return the power set, so given:
> 
> [1,2,3]
> 
> it should return:
> 
> [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
> 
> After much general confusion, this is what I eventually came up with:
> 
> def foo(pool,head,result,n):
>     """ pool, head and result should be lists, n a positive integer """
>     if (n == 0):
>        while (pool != []):
>              head.append(pool.pop())
>              result.append(head[:])
>              head.pop()
>     else:
>        while (pool != []):
>              head.append(pool.pop())
>              foo(pool[:],head,result,n-1)
>              head.pop()
> 
> def power(set):
>     head = []
>     result = [[]]
>     for i in range(len(set)):
>         foo(set[:],head,result,i)
>     return result
> 
> This gives the subsets in a simmilar order to the one in which I would find 
> them if I was doing it by hand, but its kind of difficult to think about, so 
> I thought about it a bit more and came up with:
> 
> def power(set):
>     result = []
>     bits = len(set)
>     for string in range(2**bits):
>         subset = []
>         position = 0
>         while (string > 0):
>               if (string % 2 != 0):
>                  subset.append(set[position])
>               string /= 2
>               position += 1
>         result.append(subset)
>     return result
> 
> Even though this algorithm gives the subsets in a completely different order 
> to the way I'd normally find them by hand, I'm guessing its closer to the 
> "canonical" algorithm for finding power sets than my recursive attempt, am I 
> right? or is there a third, completely different way of doing this?

Catching up...

def powerset(seq):
    if len(seq):
        head = powerset(seq[:-1])
        return head + [item + [seq[-1]] for item in head]
    else:
        return [[]]
        
Do not mix the sorting task with the plain "powersetting"! If you want
to have the powerset sorted like you prefer, you should use a
multipurpose "function sort": first by value and then by length. The
standard Python sort() already sort sequences by value.

def funcsort(seq, func):
    """ sort seq by func(item) """
    seq = seq[:]
    seq.sort(lambda x, y: cmp(func(x), func(y)))
    return seq

With these two functions your task is trivial:

>>> power_set = powerset([1, 2, 3])        # create the powerset
>>> power_set.sort()                       # sort the powerset by value
>>> funcsort(power_set, lambda x: len(x))  # sort the powerset by length


Thorsten