## Coin Change, Part 1

### May 17, 2013

The counting function loops through the coins in xs, and for each coin loops from the value of the coin to n adding the count for the current target less the current coin:

```(define (count xs n)   (let ((cs (make-vector (+ n 1) 0)))     (vector-set! cs 0 1)     (do ((xs xs (cdr xs)))         ((null? xs) (vector-ref cs n))       (do ((x (car xs) (+ x 1))) ((< n x))         (vector-set! cs x (+ (vector-ref cs x)           (vector-ref cs (- x (car xs)))))))))```

The enumerating function is the same, except that it keeps list of coins instead of counts:

```(define (coins xs n)   (let ((cs (make-vector (+ n 1) (list))))     (vector-set! cs 0 (list (list)))     (do ((xs xs (cdr xs)))         ((null? xs) (vector-ref cs n))       (do ((i (car xs) (+ i 1))) ((< n i))         (vector-set! cs i           (append (vector-ref cs i)                   (map (lambda (zs) (cons (car xs) zs))                        (vector-ref cs (- i (car xs))))))))))```

The dynamic programming aspect of the solution is obvious, as both functions use the vector cs to keep solutions to sub-problems, finally returning the value in the last element of the vector.

Here are two examples:

```> (count '(1 5 10 25) 40) 31 > (coins '(1 5 10 25) 40) ((1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1)  (5 5 5 5 5 5 5 1 1 1 1 1)  (5 5 5 5 5 5 5 5)  (10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 5 5 5 5 1 1 1 1 1 1 1 1 1 1)  (10 5 5 5 5 5 1 1 1 1 1)  (10 5 5 5 5 5 5)  (10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (10 10 5 5 1 1 1 1 1 1 1 1 1 1)  (10 10 5 5 5 1 1 1 1 1)  (10 10 5 5 5 5)  (10 10 10 1 1 1 1 1 1 1 1 1 1)  (10 10 10 5 1 1 1 1 1)  (10 10 10 5 5)  (10 10 10 10)  (25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)  (25 5 1 1 1 1 1 1 1 1 1 1)  (25 5 5 1 1 1 1 1)  (25 5 5 5)  (25 10 1 1 1 1 1)  (25 10 5))```

You can run the program at http://programmingpraxis.codepad.org/RekApsRy.

In a future exercise we will see a variant on the coin change problem where the task is to determine the smallest set of coins that sum to a particular target, without first enumerating all the possibilities.

Pages: 1 2

### 7 Responses to “Coin Change, Part 1”

1. […] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

```import Data.List

coins :: (Num a, Ord a) => [a] -> a -> [[a]]
coins _  0 = [[]]
coins xs n = [c:r | (c:cs) <- tails xs, c <= n, r <- coins (c:cs) (n-c)]

count :: (Num a, Ord a) => [a] -> a -> Int
count xs = length . coins xs
```
3. Alan S. said

Here is a Ruby program with both functions

```#!/usr/bin/env ruby
# coin-change1.rb
#
# count sets of coins (pennies, nickles, dimes, quarters) that
# add to a specific total
#
# Count the different sets of the polynomial:
#   total = P + N*5 + D*10 * Q*25
#
# A "coin set" is a 4-tuple of [P,N,D,Q]
#

\$coin_values = [ 1, 5, 10, 25 ]

# given a total, find the maximum number of coins for each
# denomination

def compute_max_coins(total)
\$max_coins = \$coin_values.map {|value| Integer(total / value)}
\$max_pennies  = \$max_coins
\$max_nickles  = \$max_coins
\$max_dimes    = \$max_coins
\$max_quarters = \$max_coins
end

# get all the coin sets for a given total

def get_coin_sets(total)
coin_sets = []
(0..\$max_quarters).each { |q|
break if total < q*25
qtotal = total - q*25
(0..\$max_dimes).each { |d|
break if qtotal < d*10
dtotal = qtotal - d*10
(0..\$max_nickles).each { |n|
break if dtotal < n*5
p = dtotal - n*5
coin_sets += [[q,d,n,p]]
}
}
}
coin_sets
end

if ARGV.size > 0
total = ARGV.shift.to_i
else
total = 40
end

compute_max_coins(total)
coin_sets = get_coin_sets(total)

puts "For total = #{total}"
puts "There are #{coin_sets.size} sets of coins"
puts ''
set = 1
printf "Set  \$.25  \$.10  \$.05  \$.01\n"
coin_sets.each do |q,d,n,p|
printf "%3d: %4d  %4d  %4d  %4d\n", set, q, d, n, p
set += 1
end

exit
```
4. aks said

Here is the output:

```\$ ./coin-change1.rb
For total = 40
There are 31 sets of coins

Set  \$.25  \$.10  \$.05  \$.01
1:    0     0     0    40
2:    0     0     1    35
3:    0     0     2    30
4:    0     0     3    25
5:    0     0     4    20
6:    0     0     5    15
7:    0     0     6    10
8:    0     0     7     5
9:    0     0     8     0
10:    0     1     0    30
11:    0     1     1    25
12:    0     1     2    20
13:    0     1     3    15
14:    0     1     4    10
15:    0     1     5     5
16:    0     1     6     0
17:    0     2     0    20
18:    0     2     1    15
19:    0     2     2    10
20:    0     2     3     5
21:    0     2     4     0
22:    0     3     0    10
23:    0     3     1     5
24:    0     3     2     0
25:    0     4     0     0
26:    1     0     0    15
27:    1     0     1    10
28:    1     0     2     5
29:    1     0     3     0
30:    1     1     0     5
31:    1     1     1     0
```
5. […] This post presents C# solutions to a coin change problem as described in https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

6. taoufik belaidi said

I have done this exercise using a simple method: I divide the total (T) by the first coin (C1). I take the integer part of this division (n1=T//c1). n1 represents the maximum number of possiblities of having c1 in any combinaison. After that, I do the same process for finding the total minus 0, 1,…, n1*c1 now using just the new set (C2, C3, C4).

Here is the program in Python, and it works well: the result is outputed very fast.

c1=25
c2=10
c3=29
c4=3

T=40

C=[]
for i in range(0, (T//c1)+1):
if T-(ic1)==0:
C.append([i,0,0,0])
continue
for j in range(0, ((T-i
c1)//c2)+1):
if T-ic1-jc2==0:
C.append([i,j,0,0])
continue
for w in range(0, ((T-ic1-jc2)//c3)+1):
if (T-ic1-jc2-wc3)%c4 == 0:
C.append([i,j,w,(T-i
c1-jc2-wc3)//c4])

for i in C:
print(i)
print(len(C))

7. […] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be […]