Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > My own accounting python euler problem

Reply
Thread Tools

My own accounting python euler problem

 
 
MRAB
Guest
Posts: n/a
 
      11-08-2009
Ozz 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
>
> Now, to use the above piece of code (after 'import subset'):
>
> >>> subset.subsets([4,7,8,2])

> [[2], [2, 4], [2, 7], [2, 7, 4], [2, 8], [2, 8, 4], [2, 8, 7], [2, 8, 7,
> 4], [], [4], [7], [7, 4], [8], [8, 4], [8, 7], [8, 7, 4]]
> >>> map(sum,subset.subsets([4,7,8,2]))

> [2, 6, 9, 13, 10, 14, 17, 21, 0, 4, 7, 11, 8, 12, 15, 19]
>
> It's not a real solution yet, and as others have pointed out the problem
> is NP complete but it might help to get you going.
>

Here's my own take on it:

def list_possible_invoices(invoices, check):
if check:
# The check hasn't yet been fully consumed.
for index, inv in enumerate(invoices):
# If this invoice doesn't exceed the check then it consume
some of the check.
if inv <= check:
# Try to consume the remainder of the check.
for inv_list in list_possible_invoices(invoices[index +
1 : ], check - inv):
yield [inv] + inv_list
else:
# The check has been fully consumed.
yield []

invoices = [500, 400, 450, 200, 600, 700]
check = 600

# List all the possible subsets of invoices.
# Sorting the invoices first in descending order lets us reduce the
number of possibilities to try.
for inv_list in list_possible_invoices(sorted(invoices, reverse=True),
check):
print inv_list

 
Reply With Quote
 
 
 
 
geremy condra
Guest
Posts: n/a
 
      11-08-2009
On Sun, Nov 8, 2009 at 11:52 AM, Dan Bishop <(E-Mail Removed)> wrote:
> On Nov 8, 4:43*am, Ozz <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
geremy condra
Guest
Posts: n/a
 
      11-08-2009
On Sun, Nov 8, 2009 at 12:31 PM, geremy condra <(E-Mail Removed)> wrote:
> On Sun, Nov 8, 2009 at 11:52 AM, Dan Bishop <(E-Mail Removed)> wrote:
>> On Nov 8, 4:43*am, Ozz <(E-Mail Removed)> 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
 
Reply With Quote
 
Ozz
Guest
Posts: n/a
 
      11-08-2009
Dan Bishop schreef:
>
> 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 []


Nice one. Thanks!

Ozz
 
Reply With Quote
 
Ozz
Guest
Posts: n/a
 
      11-08-2009
vsoler schreef:
>
> Instead of subsets, do you mean permutations/combinations? Since 2
> invoices can have the same amount perhaps the terms permutation is
> better.
>


As some other poster already suggested 'powerset' (
http://en.wikipedia.org/wiki/Power_set ) may be a better name, except
for those duplicates, of course. On the other hand, I think viewing it
as a powerset is the most 'natural' in this case. (imo permutations are
about the order of objects, not about whether the objects are included
in a set or not)

cheers,
Ozz

 
Reply With Quote
 
Gerry
Guest
Posts: n/a
 
      11-10-2009
On Nov 8, 2:42*pm, Ozz <(E-Mail Removed)> wrote:
> vsoler schreef:
>

And, of course, you'd want to take a look a this: http://xkcd.com/287/

Gerry
>
> > Instead of subsets, do you mean permutations/combinations? *Since 2
> > invoices can have the same amount perhaps the terms permutation is
> > better.

>
> As some other poster already suggested 'powerset' (http://en.wikipedia.org/wiki/Power_set) may be a better name, except
> for those duplicates, of course. On the other hand, I think viewing it
> as a powerset is the most 'natural' in this case. (imo permutations are
> about the order of objects, not about whether the objects are included
> in a set or not)
>
> cheers,
> Ozz


 
Reply With Quote
 
Steven D'Aprano
Guest
Posts: n/a
 
      11-10-2009
On Sun, 08 Nov 2009 12:31:26 -0500, geremy condra wrote:

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

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


Your test doesn't show what you think it shows. You shouldn't just
blindly apply timeit without testing to see that the functions return
what you think they return. Your test is, I'm afraid, totally bogus and
the conclusion you draw is completely wrong.


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


For the sake of speed, I've used a smaller x. Here are the results of
calling the three functions:


>>> x = range(3)
>>> subsets1(x)

[[2], [2, 0], [2, 1], [2, 1, 0], [], [0], [1], [1, 0]]
>>> subsets2(x)

<generator object subsets2 at 0xb7c6311c>
>>> subsets3(x)

<itertools.chain object at 0xb7c608ac>

The reason subsets1() "doesn't appear to terminate" is that you are
trying to list all the subsets of x = range(100). That's a LOT of
subsets: 2**100 to be precise, or approximately 1.2e30.

subsets2() and subsets3() return a generator function and an iterator
object respectively. There may be some overhead difference between those,
but that's trivial compared to the cost of generating the subsets
themselves.

A better way of doing the timing is as follows:



from itertools import chain, combinations
from timeit import Timer

# use a number small enough to calculate in a reasonable time
x = list(range(10))

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 subsets2(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))

setup = "from __main__ import subsets1, subsets2, subsets3, x"


# Check the three functions return the same results:
x1 = sorted(subsets1(x))
x2 = sorted(subsets2(x))
x3 = sorted(list(t) for t in subsets1(x))
assert x1 == x2 == x3

# Set up some timers.
t1 = Timer("subsets1(x)", setup)
t2 = Timer("list(subsets2(x))", setup)
t3 = Timer("list(subsets3(x))", setup)

# And run them!
for t in (t1, t2, t3):
print min(t.repeat(number=1000, repeat=5))



The results I get are:

1.19647693634
0.901714801788
0.175387859344

Which as you can see, shows that the recipe in the docs is nearly ten
times faster than Dan's version. That's not surprising -- the docs
version uses highly optimized C code from itertools, while Dan's version
uses slow-ish Python code and recursion.


To show this is no fluke, I increased the size of x and ran the tests
again:


>>> x = list(range(15)) # 32000+ subsets
>>> x1 = sorted(subsets1(x))
>>> x2 = sorted(subsets2(x))
>>> x3 = sorted(list(t) for t in subsets1(x))
>>> assert x1 == x2 == x3
>>>
>>> t1 = Timer("subsets1(x)", setup)
>>> t2 = Timer("list(subsets2(x))", setup)
>>> t3 = Timer("list(subsets3(x))", setup)
>>> for t in (t1, t2, t3):

.... print min(t.repeat(number=1000, repeat=5))
....
45.283468008
33.9274909496
7.40781188011



--
Steven
 
Reply With Quote
 
geremy condra
Guest
Posts: n/a
 
      11-10-2009
On Tue, Nov 10, 2009 at 8:59 AM, Steven D'Aprano
<(E-Mail Removed)> wrote:
> On Sun, 08 Nov 2009 12:31:26 -0500, geremy condra wrote:
>
>> What you're describing is the powerset operation. Here's the example
>> from the python docs:

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

>
> Your test doesn't show what you think it shows. You shouldn't just
> blindly apply timeit without testing to see that the functions return
> what you think they return. Your test is, I'm afraid, totally bogus and
> the conclusion you draw is completely wrong.


<snip>

Doh! I even noticed that the asymptotic times didn't match up
and still blew right past the obvious answer. Thanks (again) for
the correction, Steven.

Geremy Condra
 
Reply With Quote
 
MRAB
Guest
Posts: n/a
 
      11-10-2009
Gerry wrote:
> On Nov 8, 2:42 pm, Ozz <(E-Mail Removed)> wrote:
>> vsoler schreef:
>>

> And, of course, you'd want to take a look a this: http://xkcd.com/287/
>

I've found 2 solutions.

(And I really should get back to what I was doing...)

> Gerry
>>> Instead of subsets, do you mean permutations/combinations? Since 2
>>> invoices can have the same amount perhaps the terms permutation is
>>> better.

>> As some other poster already suggested 'powerset' (http://en.wikipedia.org/wiki/Power_set) may be a better name, except
>> for those duplicates, of course. On the other hand, I think viewing it
>> as a powerset is the most 'natural' in this case. (imo permutations are
>> about the order of objects, not about whether the objects are included
>> in a set or not)
>>
>> cheers,
>> Ozz

>


 
Reply With Quote
 
Mel
Guest
Posts: n/a
 
      11-10-2009
Gerry wrote:

> On Nov 8, 2:42 pm, Ozz <(E-Mail Removed)> wrote:
>> vsoler schreef:
>>

> And, of course, you'd want to take a look a this: http://xkcd.com/287/


I remember that.

mwilson@tecumseth:~/sandbox$ python xkcd_complete.py
[1, 0, 0, 2, 0, 1] 1505
[7] 1505

Mel.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Python is awesome (Project Euler) Roy Smith Python 6 01-03-2013 02:38 AM
python scripts solution for euler projects scripts examples Python 2 03-01-2012 02:19 AM
Pr. Euler 18, recursion problem process Python 4 10-09-2008 05:39 PM
Why is this loop heavy code so slow in Python? Possible Project Euler spoilers Bruno Desthuilliers Python 30 09-19-2007 04:59 PM
Euler tour problem Piet den Dulk Java 6 10-27-2003 08:34 PM



Advertisments