Algorithm for determining number of possible combinations

Question

I need to write an algorithm for a given problem: You have infinite pennies, nickels, dimes, and quarters. Write a class method that will output all combinations of coins such that the total is 99 cents.

It seems like a permutation nPr problem. Any algoritham for it?

Regards, Priyank

possible duplicate of [Find all combinations of coins when given some dollar value](http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value) — Paul R, Jun 13 '12 at 09:34

score 1 · Answer 1 · answered Jun 17 '14 at 21:55

I think this problem is most easily answered using recursion w a table of denominations

{5000, 2000, ... 1} // $50's to one penny

You would start with:

WaysToMakeChange(10000, 0) // ie. $100...highest denomination index is 0 ($50)

WaysToMakeChange(amount, maxdenomindex) would calculate using 0 or more of the maxdenom
the recurance is something like
WaysToMakeChange(amount - usedbymaxdenom, maxdenomindex - 1)

I programmed this and it can be optimized in many ways:

1) multithreading

2) caching. This is very important. B/c of the way the algorithm works, WaysToMakeChange(m,n) will be called many times with the same initial values: For example. Changing $100 can be done by: 1 $50 + 0 $20's + 0 $10's + ways to $50 dollars with highest currency $5 (ie. WaysToMakeChange(5000, index for $5) 0 $50 + 2 $20's + 1 $10's + ways to $50 dollars with highest currency $5 (ie. WaysToMakeChange(5000, index for $5) Clearly WaysToMakeChange(5000, index for $5) can be cached so that the subsequent call does not need to be made

3) Shortcircuiting the lowest recursion. Suppose static const int denom[] = {5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1};

The first test for WaysToMakeChange(int total, int coinIndex) should be something like: if( coins[_countof(coins)-1] == 1 && coinIndex == _countof(coins) - 2){ return total / coins[_countof(coins)-2] + 1; }

What does this mean? Well if your lowest denom is 1 then you only have to go as far as the second lowest denom (say a nickel). Then there are 1+ total/second lowest denom left. For example: 49c -> 5 nickels + 4 pennies. 4 nickels + 9 pennies....49 pennies = 1+ total/second lowest denom left

score 0 · Answer 2 · 2012-06-16T00:03:37.523

This problem seems like it is a diophantine equation, i.e. for a*x + b*y + ... = n, find a solution, where all letters are integers. The simplest, but not the most elegant solution would be an iterative one (displayed in python, note that I skip variable l because it resembles the number 1):

dioph_combinations = list()
for i in range(0, 99, 25):
    for j in range(0, 99-i, 10):
        for k in range(0, 99-i-j, 5):
            for m in range(0, 99-i-j-k, 1): 
                if i + j + k + m == 99:
                    dioph_combinations.append( (i/25, j/10, k/5, m) )

The resulting list dioph_combinations will contain the possible combinations.

Same algorithm, but dropping the unnecessary `m` loop and unnecessary repeated calculations: http://coliru.stacked-crooked.com/a/69bb565a78bac539 — Mooing Duck, Jun 17 '14 at 22:16

score 0 · Answer 3 · answered Jun 13 '12 at 09:15

0

The easiest way is probably to spend a few moments thinking about the problem. There is a relatively nice, recursive, algorithm that lends itself neatly to either memoization or reworking into a dynamic programming solution.

answered Jun 13 '12 at 09:15

Vatine

20,782
4
54
70

2

+1: while I think that the easiest way now seems to be 'ask SO and someone will do my work for me' you suggest a much better approach. – High Performance Mark Jun 13 '12 at 09:20
@HighPerformanceMark: Yes, I tried to give an answer that, while helpful, doesn't give the whole thing away. If I am assured that this is not homework (or is homework, with some evidence of thought given), I might even furnish it with more details. – Vatine Jun 13 '12 at 09:21

score 0 · Answer 4 · answered Jun 13 '12 at 18:37

This problem is classic Dynamic Programming problem. You can read about it here

http://www.algorithmist.com/index.php/Coin_Change

the python code is:

def count( n, m ):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m <= 0 and n >= 1:
        return 0

    return count( n, m - 1 ) + count( n - S[m], m )

Here S[m] gives the value of the denomination and S is a sorted array of denominations

Algorithm for determining number of possible combinations

4 Answers4