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$
10
  • 3
    $\begingroup$ IntegerPartitions[100, 4, {25, 50}] ? $\endgroup$ Dec 17, 2015 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, 2015 at 19:00
  • $\begingroup$ @Dr.belisarius, @march IntegerPartitions is too memory-hungry for large integers, unfortunately. $\endgroup$
    – shrx
    Dec 17, 2015 at 19:02
  • $\begingroup$ Also, it's deterministic. $\endgroup$
    – shrx
    Dec 17, 2015 at 19:08
  • 3
    $\begingroup$ Also FrobeniusSolve[{25, 50}, 100] $\endgroup$ Dec 17, 2015 at 19:13

1 Answer 1

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$
3
  • $\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, 2015 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, 2015 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, 2015 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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