Keith Winston <keithw...@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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
