## 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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 \$ ./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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 #!/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

view raw

coin-change1.rb

hosted with ❤ by GitHub

```#!/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 […]