My own accounting python euler problem

[geremy condra]

On Sun, Nov 8, 2009 at 11:52 AM, Dan Bishop <danb_83 at yahoo.com> wrote:
> On Nov 8, 4:43 am, Ozz <notva... at wathever.com> wrote:
>> Hi,
>>
>> > My first question is:
>> > 1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
>> > check Ch=600
>> > how can I print all the different combinations of invoices that the
>> > check is possibly cancelling
>>
>> Incidentally, I'm currently learning python myself, and was working on
>> more or less the same problem as an exercise;
>>
>> For listing all different subsets of a list (This is what I came up
>> with. Can it be implemented shorter, btw?):
>>
>> def subsets(L):
>>          S = []
>>          if (len(L) == 1):
>>                  return [L, []]
>>          else:
>>                  for s in subsets(L[1:]):
>>                          S.append(s)
>>                          S.append(s + [ L[0]])
>>          return S
>
> You can avoid the S list my making it a generator:
>
> def subsets(L):
>    if L:
>        for s in subsets(L[1:]):
>            yield s
>            yield s + [L[0]]
>    else:
>        yield []

What you're describing is the powerset operation. Here's the example
from the python docs:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

What I find interesting is that running it through timeit, it is much
slower than the code suggested by Dan Bishop.

setup = """
from itertools import chain, combinations

x = list(range(100))

def subsets1(L):
       S = []
       if (len(L) == 1):
               return [L, []]
       else:
               for s in subsets1(L[1:]):
                       S.append(s)
                       S.append(s + [ L[0]])
       return S

def subsets2(L):
   if L:
       for s in subsets(L[1:]):
           yield s
           yield s + [L[0]]
   else:
       yield []

def subsets3(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
"""

#timeit.timeit("subsets1(x)", setup) doesn't appear to terminate
timeit.timeit("subsets2(x)", setup)
timeit.timeit("subsets3(x)", setup)


I'm getting numbers roughly 3:1 in Dan's favor.

Geremy Condra