My own accounting python euler problem

[geremy condra]

On Sun, Nov 8, 2009 at 12:31 PM, geremy condra <debatem1 at gmail.com> wrote:
> 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
>

I made a mistake copying it on line 18 of the above; it should be
subsets2, rather than just subsets.

Geremy Condra