Coin Change Algorithm with limited coins - Scheme

Question

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)

As a rule of thumb, you almost never need `length`. `(<= (length coins) 0)` is true when `(empty? coins)` is, but it's much slower. — molbdnilo, Apr 01 '21 at 11:48
@molbdnilo: for some reason, i'm not allowed to use (empty?).. But if i'll do (eq? coins '()), will it make any difference to time complexity? — ryden, Apr 01 '21 at 13:54
Are you able to change how you take your input? Because right now it, with how you take your input, you are defining each coin as a separate entity meaning that the choice to include or exclude each coin is different. It sounds like you want to treat coins as a group rather than individuals in which case you should use a list of 2-lists. Your function doesn't work as is because each 1 is getting paired with 2 2s — Ryan Schaefer, Apr 02 '21 at 20:22
@RyanSchaefer: Hello, Yes, i'm allowed to change my input, as long as i "remmember" the quantity of each coin and avoid duplications. Right now, my algorithm won't work for that, i know. I'm still trying to fix it or find a better solution. What was the method you mentioned? Using list of 2-lists. I'd really like to know:) — ryden, Apr 04 '21 at 13:02

score 1 · Accepted Answer · edited Apr 05 '21 at 12:28

1

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!

edited Apr 05 '21 at 12:28

Will Ness

70,110
9
98
181

answered Apr 05 '21 at 09:29

ryden

189
6

can you prove it's correct? what was your thought process? the answer could benefit from some elaborations. – Will Ness Apr 05 '21 at 12:31
i've done a lot of tests and it worked. The idea of the recursive cal was: at each step i look at the first coin in the list and i chose whether i take it or not. In the first recursive call i choose to take the coin into the sum and remove it from the list(can't use the same coin twice). in the second recursive call i choose not to take the coin and not any of the other coins that has the same value. – ryden Apr 05 '21 at 17:51
you've described your code in words, but the question is, does it count all the lawful solutions, and does it count none of them more than once. in any case that explanation belongs in the answer's body. :) – Will Ness Apr 05 '21 at 17:56
well, i'm not sure i know how to prove it's correctness formally. i never was too good at that :\ except for bunch of different and sophisticated tests that worked fine, i have nothing.. – ryden Apr 06 '21 at 07:55

score 0 · Answer 2 · answered Apr 04 '21 at 16:45

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

interesting... i gotta try this out. but i gotta find a way to convert my input list into this 2-list, like in your example: ``` '(1 1 1 2 2 5 10) → '((1 3) (2 2) (5 1) (10 1)) ``` how can i do it in the easiest way? — ryden, Apr 04 '21 at 16:57
but you've said you're open to [changing the input](https://stackoverflow.com/questions/66892992/coin-change-algorithm-with-limited-coins-scheme#comment118328264_66892992). so just write it this way in the first place. otherwise, it's a separate question. _or_ you can adjust this algorithm to work on that your data... you said you wanted to know what does _working with 2-lists_ mean; this answer shows this. how to write it in Scheme syntax is a separate issue. you could post your attempts and ask a new question, if needed. (with the link back to this one). — Will Ness, Apr 04 '21 at 22:10
(in any case that transformation is known as RLE, "run-length encoding". there should be lots of code to be found under that search phrase) — Will Ness, Apr 05 '21 at 06:57

Coin Change Algorithm with limited coins - Scheme

2 Answers2