[Tutor] Euler Spoiler

[Dave Angel]

 Keith Winston <keithwins at gmail.com> Wrote in message:
> 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.

Care to define "bogging down"?  If you mean it gets REALLY slow
 then I'm not surprised.  Do you have any idea how many
 combinations there are for even a moderate sized list of
 coins?

For the call  combinations(tcombo, k + 1) with k =99 and tcombo of
 size 200, the number of iterations has 59 digits.  With a really
 fast computer you might scratch the surface in a trillion
 trillion trillion years.

One way to improve on that enormously would be to scrap tcombo and
 call itertool.combinations_with_replacement. But I think the
 notion of generating all combinations and then selecting is
 doomed to failure for all but the smallest problems.

Incidentally I think you have way too many nested loops. Even if
 brute force were going to work,  you'd do it with
 itertool.combinations_with_replacement(coins without doing combo
 or tcombo. 


-- 
DaveA



----Android NewsGroup Reader----
http://www.piaohong.tk/newsgroup