CODEWITHSUNDEEP
algorithmschemeracketcoin-change
ryden
ryden

Reputation: 189

Coin Change Algorithm with limited coins - Scheme

i need to write the procedure change which gets a sum of money and list of available coins, and returns the number of possible ways to pay the money with these coins. And as i said, the coins are limited.

Examples:

(change 10 '(5 5 10)) → 2
;; [1 coin of 10 ,2 coins of 5]

(change 5 '(1 1 1 2 2 5 10)) → 3
;; [1 coin of 5, 1 coin of 2 and 3 coins of 1, 2 coins of 2 and 1 coin of 1]

I tried this:

(define (change sum coins)
  (if (< sum 0)
      0
      (if (= sum 0)
          1
          (if (and (> sum 0) (<= (length coins) 0))
            0
            (+ (change (- sum (car coins)) (cdr coins)) 
               (change sum (cdr coins)))))))

But i couldn't get rid of some duplicates counts... instead of 3, my output for the 2nd example was:

(change 5 '(1 1 1 2 2 5 10)) → 6

What can be done to fix this problem?

(The code should be run in Racket, purely functional and not using any build-in methods. I prefer recursive. The only data structures that allowed are List and Pair)

Upvotes: 1

Views: 573

Answers (2)

ryden
ryden

Reputation: 189

Done it! My algorithm was simple, using this remove-all method:

(define remove-all
  (lambda (x lst)
    (if (empty? lst)
        '()
    (if (= (car lst) x)
        (remove-all x (cdr lst))
    (cons (car lst) 
          (remove-all x (cdr lst)))))))

(define payment
    (lambda (n coins-lst)
        (if (< n 0)
            0
        (if (= n 0)
            1
        (if (and (> n 0) (empty? coins-lst))
            0
        (+ (payment  (- n (car coins-lst))  (cdr coins-lst)) 
           (payment n (remove-all (car coins-lst) coins-lst))))))))

Thanks for all your advice!

Upvotes: 1

Will Ness
Will Ness

Reputation: 71065

Unlimited coin-change is:

ways( 0  , _ ) = 1
ways( sum, _ ) | sum < 0 = 0
ways( sum, 0 ) | sum > 0 = 0
ways( sum, k ) = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k )

which is

               = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k - 1 )
                 +
                 ways( sum - 2*first_denomination(k),  k )
               = ......
                 ......
               = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k - 1 )
                 +
                 ways( sum - 2*first_denomination(k),  k - 1 )
                 +
                 ways( sum - 3*first_denomination(k),  k - 1 )
                 +
                 ......

(up to the base cases). Hence, the limited coin-change is

ways( sum, [ [c, n], ...t] ) = 
                 ways( sum, t )           ; taking none of c
                 +
                 ways( sum - c,  t )      ; taking one of c
                 +
                 ways( sum - 2*c,  t )    ; taking two of c
                 +
                 ...
                 +
                 ways( sum - n*c,  t )    ; taking n c-valued coins

with the properly adjusted base cases.

All that's left is to write this thing down in the Scheme syntax, so you could call it as

(change 5 '((1 3) (2 2) (5 1) (10 1)) ) → 3

Upvotes: 0

Related Questions