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. I'm sure there are wholly different approaches, feel free to hint at them, but my real question is: is there any further fine-tuning of my approach (or any outright problems with it) that would be instructive? Thanks! Also: I think it might have worked better with lists that tuples, though I don't really understand why, unless I misunderstand speed or memory management issues (or something else). from itertools import combinations coins = [100, 50, 20] # should include 1, 2, 5, 10 (plus one 200 combo) ans = set() goal = 200 tcombo = () # Iterate over all possible length combinations of coins for i in range(len(coins)): print(i) # For each unique combo of coins, and... for combo in combinations(coins, i+1): tcombo = () # For each coin in that combo... for coin in combo: # create a new tuple of as many of those coins as # it would take to reach the goal tcombo = tcombo + (coin,) * int(goal/coin) # with this new extended list, generate all possible length combinations for k in range(len(tcombo)): for c in combinations(tcombo, k + 1): if sum(c) == goal: ans = ans | {c} print(ans) -- Keith _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor