5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ IntegerPartitions[100, 4, {25, 50}] ? $\endgroup$ – Dr. belisarius Dec 17 '15 at 19:00
  • $\begingroup$ Have you looked at IntegerPartitions? For instance, IntegerPartitions[100, All, {25, 50}] generates your first example. I expect that IntegerPartitions 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 do RandomSample. $\endgroup$ – march Dec 17 '15 at 19:00
  • $\begingroup$ @Dr.belisarius, @march IntegerPartitions is too memory-hungry for large integers, unfortunately. $\endgroup$ – shrx Dec 17 '15 at 19:02
  • $\begingroup$ Also, it's deterministic. $\endgroup$ – shrx Dec 17 '15 at 19:08
  • 3
    $\begingroup$ Also FrobeniusSolve[{25, 50}, 100] $\endgroup$ – Dr. belisarius Dec 17 '15 at 19:13
6
$\begingroup$

Use RandomChoice with FindInstance

denom = {penny, nickel, dime, quarter, half, dollar};
value = {.01, .05, .1, .25, .5, 1};

instance[total_, n : _Integer?Positive : 100] :=
 RandomChoice[FindInstance[
   denom.{1, 5, 10, 25, 50, 100} == 
     100 total &&
    (And @@ Thread[denom >= 0]),
   denom, Integers, n]]

instance[1.67]

(*  {penny -> 62, nickel -> 0, dime -> 8, quarter -> 1, half -> 0, 
 dollar -> 0}  *)

denom.value /. %

(*  1.67  *)

instance[1.67]

(*  {penny -> 52, nickel -> 11, dime -> 1, quarter -> 0, half -> 1, 
 dollar -> 0}  *)

denom.value /. %

(*  1.67  *)

instance[2.33, 1000]

(*  {penny -> 78, nickel -> 9, dime -> 1, quarter -> 2, half -> 1, 
 dollar -> 0}  *)

denom.value /. %

(*  2.33  *)
$\endgroup$
  • $\begingroup$ I modified the code a bit to better suit the question, I hope it's ok. FindInstance is itself non-deterministic, so we don't need to wrap it in RandomChoice. $\endgroup$ – shrx Dec 18 '15 at 8:45
  • $\begingroup$ @shrx - I returned my answer to original. Your edits caused instance to return the same result for the same input rather than varying the result for each call. Recommend that you put your response in a separate answer. $\endgroup$ – Bob Hanlon Dec 18 '15 at 17:44
  • $\begingroup$ That's interesting. I have checked the output for multiple solutions and it is different every time. But I didn't check the output for a single solution, where it appears the result will always be the same. Maybe it's worth opening a separate question about this. $\endgroup$ – shrx Dec 18 '15 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.