Hi Keith,
On 12 January 2014 23:12, Keith Winston <keithw...@gmail.com> wrote:
> I'm working through some of the Project Euler problems, and the
> following might spoil one of the problems, so perhaps you don't want
> to read further...
>
>
> The problem relates to finding all possible combinations of coins that
> equal a given total. I'm basically brute-forcing it, which is probably
> not the way to go, but has already taught me a good bit about sets,
> tuples, and iterators, so... so far so good.
>
> However, after all the refactoring I can think of, I can't get it past
> a 3-coin list without it bogging down.
>
Sorry I haven't got time to look at your attempt closely (nearly 1am here),
but try/have a look at this:
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
#Taken from: http://docs.python.org/2/library/itertools.html
#(It doesn't strictly operate on or generate sets as can be seen.)
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
coins = [100, 50, 20, 20, 10, 10, 10]
goal = 200
solutions = set(list(s for s in powerset(coins) if sum(s) == goal))
print solutions
# outputs: set([(100, 50, 20, 20, 10), (100, 50, 20, 10, 10, 10)])
Walter
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
