My own accounting python euler problem

geremy condra debatem1 at gmail.com
Sun Nov 8 18:31:26 CET 2009

```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

```