How to solve coin change task when order does matters?

Question

As I found in here,

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d_1....d_m. It is a general case of Integer Partition, and can be solved with dynamic programming.

The problem is typically asked as: If we want to make change for N cents, and we have infinite supply of each of S = { S_1, S_2,....., S_m } valued coins, how many ways can we make the change? (For simplicity's sake, the order does not matter.)

I tried this and this works fine. So How I can modify this to find all possible coin combinations when the order of different coins actually does matter.

i.e. : before

For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

now :

for N = 4,S = {1,2,3}, there are 7 solutions: {1,1,1,1},{1,1,2},{1,2,1},{2,1,1},{2,2},{1,3},{3,1}

here {1,1,1,1} even though one can pick the four '1's in different order it has to be considered as one final combination. rather than considering that four coins are different. so actually the order of different coins has to be different to count it as a separate combination.

ex: {1,1,3} won't assume {1_a,1_b,3_a} is a combination and {1_b,1_a,3_a} is another combination with different ordering.

Answer 1

The current recursive implementation is very simplified. It only passes the remaining value and the index of the possible denominations. If you passed an array of denominations when you got to n==0 you could add another check to see if you have that combination already. If you do return 0 otherwise return 1.

This is a dynamic solution and requires much more memory than the other solution but it will get you the answer.

func count(n, m, p[])
//regular if checks with additional nested if in (n == 0)
return count( n, m - 1, p[] ) + count( n - S[m], 0, p[] + S[m] )

in this pseudo code p[] + S[m] just means to add S[m] to the next available position in p[]

EDIT:

Forgot to add in that you need to reset m when you dive down

// n is remaining value
// m is index of S array
// p[] is array of coins used
// solutions[] is an array of p[] arrays
func count( n, m, p[]) {
  if n == 0
    if (p[] not in solutions[]){
      solutions[].add(p[])
      return 1
    }else{
      return 0
    }
  if n < 0
    return 0
  if m <= 0 and n >= 1
    return 0
  return count(n, m - 1, p[]) + count( n - S[m], 0, p[].add(S[m]))
}

By starting with an empty array p[] each time you add a coin to the possible set you append that value to the array. When you get to the point where you've found a solution you see if it's unique. If so you add it to the count otherwise you ignore it. Because m is reset each time it will traverse all possible permutations.

Answer 2

Calculating just the number of solutions is much less effort than enumerating them all.

Lets take the example of S={1,2,3}, and call f(n) the number of solutions for amount n.

Then we have:

f(n) = 0 if n < 0

f(0) = 1

f(n) = f(n-1) + f(n-2) + f(n-3) if n > 0 (where the numbers 1,2,3 are the elements of S)

It is not too difficult to write a program performing these calculations. You could start with the low numbers and work your way up:

f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 7
f(5) = 13
...

For this specific S it turns out each number is just the sum of the preceding three numbers.

How to arrive at this formula? I take again the specific set S={1,2,3} as example, the general case is likewise easy. To count the number of solutions for n look at the first element. It can be 1, 2, or 3. If it is 1, there are f(n-1) ways to arrange the remaining elements. If it is 2 there are f(n-2) ways for the remaining elements and finally if it is 3 there are f(n-3) ways for the remaining elements. The total number must therefore be the sum of the three.

Answer 3

If you're referring to the "Dynamic programming" algorithm in the referenced Wikipedia page, I think you can just change

table[ i, j ] = table[ i - S_j, j ] + table[ i, j - 1 ]

to

table[ i, j ] = table[ i - S_j, m ] + table[ i, j - 1 ]

but I'm not 100% sure yet. The point is that in the original problem, when you are examining coin S_j, you want to add in the number of possible solutions when the amount is i - S_j but only with coins up through S_j, so that you don't get permutations of a previous sequence. By changing it to table[i - S_j, m], you do count the permutations.

EDIT: On looking into it further, I believe that this is correct but equivalent to Henry's answer, which is much simpler. This version of the problem (counting all permutations) doesn't need values to be stored in a 2-D array, the way the original one does.