I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for it. In the case of this testset the solution is 16.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2 etc 5, 5, 2, 1 10, 1, 1, 1 10, 2, 1 Total number of ways: 16
I've first tried making a list of these permutations, but that generally was slow and unwieldy. There is no need to give every permutation just the amount of them: 7/10 test cases were able to be done under 5 seconds.
So I went looking around and found this. Where a Haskell solution to a similar problem was used. I just had to make it more general for my needs and translate it in a language I could actually run (e.g. Python). I did and I ended up with the following:
def change(list, number): if (number is 0): return 1 if (len(list) is 0): return 0 if (number < list): return 0 return change(list, (number - list)) + change(list[1:], number) print(change([1, 2, 5, 10], 13)) #prints 16 (list needs to be in order btw)
This solution is better then the first one: 9/10 test cases succeeded. However this can be done better! I've yet to talk about the constraints of this assignment.
- There are no more then 8 unit coins (
len(unit_coins) <= 8)
- The unit coins are never more then 250 (
unit_coin <= 250)
- The amount of money is between 0 and 300 (
0 < money < 300)
- There is always a unit coin with a value of 1
The last part is important (you can tell, because I've highlighted it). The current solution is absolutely not taking advantage of that, and I thing there's a lot to be gained when this is used in the function.
Does anyone have an idea how to to the thing I just described. Any help would be greatly appreciated. More general answers are also welcomed as this type of optimization isn't exclusive to this perticular algorithm.
P.S. I know Python isn't a very quick language, but that's not the point of this exercise. This exercise is about making the whole algorithm better, not just a specific implementation in a certain language.