This problem is described in the related StackOverflow question: Find all combinations of coins when given some dollar value.
I would like generate a list of $n$ combinations of values that sum up to a certain number. For example, these are 3 ways to obtain the number 100
using the values {25, 50}
:
25*4
25*2 + 50*1
50*2
To calculate the combinations, I have adapted the recursive algorithm from python found here. My adapted code in Mathematica looks like this:
makeChange[value_Integer, denominations_List, soln_List, nsol_: 0] :=
Module[{solution = soln, partial},
If[nsol != 0 ∧ Length[solutions] >= nsol,
Return[];
];
If[value == 0,
AppendTo[solutions, solution];
Return[];
];
If[denominations == {},
Return[];
];
With[{firstCoin = First@denominations, tail = Rest@denominations},
With[{n = Floor[value/firstCoin]},
Do[
If[n - ix > 0,
partial = Append[solution, {firstCoin, n - ix}],
partial = solution
];
makeChange[value - (n - ix)*firstCoin, tail, partial, nsol];
, {ix, 0, n}];
makeChange[value, tail, solution, nsol];
]
]
]
And can be called like this:
solutions = {};
makeChange[100, {25, 50}, {}, 3];
solutions // Column
{{25,4}} {{25,2},{50,1}} {{50,2}}
Now, the code works ok but I have two major concerns.
1) It is slow when there are a large number of possible combinations. Can the performance be improved, maybe with memoization?
2) As it is, the algorithm is deterministic and will always return the same first $n$ solutions. Can the code be adapted to make it non-deterministic, so the solutions' order would be random? This will be useful when doing statistical analysis on a smaller sample of a very large set of solutions.
Note that I am not looking for solutions that only calculate a number of possible solutions. I need the actual solutions for statistical analysis. I am also not looking just for the optimal solution, I need to be able to calculate all of them.
Update:
Thanks to @Dr.belisarius' and @march's comments, I considered using the built-in IntegerPartitions
and FrobeniusSolve
.
The performance of IntegerPartitions
is quite good with my test problem if the number of solutions is not too large (it uses a lot of memory):
t = Rationalize@{2.3, 3.06, 3.92, 4.1, 5.74, 7.8, 7.5, 8.5, 0.68, 0.72, 0.81, 0.92, 1.02, 1.07, 1.12};
AbsoluteTiming[
solip = IntegerPartitions[1000/(GCD @@ t), All, t/(GCD @@ t), 100000];
]
{0.882162, Null}
However, FrobeniusSolve
is too slow to find even 100 solutions and seems to run forever.
AbsoluteTiming[
solf = FrobeniusSolve[t/(GCD @@ t), 1000/(GCD @@ t), 100];
]
$Aborted
Both built-in functions are also deterministic.
IntegerPartitions[100, 4, {25, 50}]
? $\endgroup$ – Dr. belisarius Dec 17 '15 at 19:00IntegerPartitions
? For instance,IntegerPartitions[100, All, {25, 50}]
generates your first example. I expect thatIntegerPartitions
will be nice and optimized, but I'm not sure because I don't know enough about it, which is why for now I'm only posting a comment. As for randomizing the list, you could doRandomSample
. $\endgroup$ – march Dec 17 '15 at 19:00IntegerPartitions
is too memory-hungry for large integers, unfortunately. $\endgroup$ – shrx Dec 17 '15 at 19:02FrobeniusSolve[{25, 50}, 100]
$\endgroup$ – Dr. belisarius Dec 17 '15 at 19:13