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
More information about the Python-list
mailing list