Coins all combinations - strange difference between 2 algorithms

Question

I was trying to solve a coin changing problem. Since I live in Europe let’s make it an Euro problem. We need 5 Euro. We can use 10, 20, 50 cents, 1 euro, 2 euro and 5 Euro. How many possibilities there are to get 5 Euro?

That’s the code that leif posted here.

cents = 50
denominations = [50, 20, 10, 5, 2, 1]
names = {50: "", 20: "", 10 : "", 5 : "", 2 : "", 1: ""}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
            comb.append( (left, denominations[i]) )
            i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

print count_combs(cents, 0, [], None)

It works great, but since this code is very difficult for me (this recursion works here only with the help of magic) I used another code, that is pretty simple for me to understand.

def money(goal, money_avail, money_used):
    if sum(money_used) == goal:
        yield money_used
    elif sum(money_used) > goal:
        pass
    elif money_avail == []:
        pass
    else:
        for change in money(goal,money_avail[:], money_used+[money_avail[0]]):
            yield change
        for change in money(goal,money_avail[1:], money_used):
            yield change


results = []
for s in money(50, [1,2,5,10,20,50], []):
    results.append(s)

cn = 0
for i in results:
    cn+=1
    i = str(i)
    print cn, i

print len(results)

They both gave me the same length of answer - there are 451 possibilities.

def is_5euro(L):
    return sum(L) == 5.0

moneybag = []
for c10 in range(51):
    for c20 in range(26):
        for c50 in range(11):
            for e1 in range(6):
                for e2 in range(3):
                    for e5 in range(2):
                        denom = [c10 * 0.1, c20 * 0.2, c50 * 0.5, e1 * 1, e2 * 2, e5 * 5]
                        if is_5euro(denom):
                            moneybag.append([c10, c20, c50, e1, e2, e5])

print len(moneybag)

But this solution gives us only 446 possibilities.

So I checked what’s the difference between list results and the third (moneybag for for for) algorithm doesn’t seem to be considering as a possibility a situation when we have:

>>>
[[0, 0, 0, 0, 1, 48], [0, 0, 0, 0, 2, 46], [0, 0, 0, 0, 23, 4], [0, 0, 0, 0, 24, 2], [0, 0, 0, 1, 2, 41]]

(48 x 10) + (1 x 20) cents
(46 x 10) + (2 x 20) cents
(4 x 10) + (23 x 20) cents
(2 x 10) + (24 x 20) cents
(41 x 10) + (2 x 20) + (1 x 50) cents

This seems to be ridiculous. Do you know why it doesn't work like the 1st and 2nd algorithms?

Have you tried to print out what does `is_5euro(L)` return for those cases? [This question](http://stackoverflow.com/a/588029) and other linked ones are related most likely. — Lafexlos, Mar 18 '16 at 09:34
@Lafexlos not really, only the list of answers. That's how I created the list of missing elements. If the algorithm works with any of the above, the result would be 50. For instance sum[0,0,0,0,1x2,48x1]. — Tom Wojcik, Mar 18 '16 at 09:39
You can try adding each subset and increment possibilities by 1 if it adds up to 5 euros? — Abhishek Kusnoor, Mar 18 '16 at 09:50

Muhammad Tahir · Accepted Answer · 2016-03-18T09:45:32.010

5

The problem is Floating Point Arithmetic: Issues and Limitations In Python. Float values are not always they seem to be. You think

(48 x 10) + (1 x 20) cents = 5.0

But originally python considers it 5.000000000000001. Which is not equal to 5.0, hence, is_5euro returns False.

You can test this by

sum([48*0.1, 1*0.2, 0*0.5, 0*1, 0*2, 0*5])

As suggested by @Tom you should use integers. You can change your denom to

denom = [c10 * 10, c20 * 20, c50 * 50, e1 * 100, e2 * 200, e5 * 500]

and your is_5euro to

def is_5euro(cents_list):
    return sum(cents_list) == 500

and it should work.

edited Mar 18 '16 at 09:45

answered Mar 18 '16 at 09:36

Muhammad Tahir

5,006
1
19
36

2

Good observation. It's also clear that floating point should *not* be used for this. This is a discreet problem, and all the math should be done with integers. The solution is to keep everything in cents rather then euros, with the goal being 500 cents. Then you have 10, 20, 50, 100, 200, and 500 as your denominations, all integers. Or you can make the unit 10 cents, and use 1, 2, 5, 10, 20, and 50, as the first solution does. – Tom Karzes Mar 18 '16 at 09:41
@TomKarzes you are right, I would use integers too. – Muhammad Tahir Mar 18 '16 at 09:42
WOW! That's true. Thank you! I would never figure it out by myself. – Tom Wojcik Mar 18 '16 at 09:43
Yeah, no need to explain. I just missed that 5.0 != (48*0.1) + (1*0.2) Clever bug, stupid me. – Tom Wojcik Mar 18 '16 at 09:56

Tom Karzes · Answer 2 · 2016-03-18T10:34:55.480

I know you aren't looking for a new solution, but just for grins, I thought I'd post the simplest solution I could come up with:

def coin_combos(goal, unit_list):
    if goal == 0:
        return [[0] * len(unit_list)]

    if len(unit_list) == 0:
        return []

    unit = unit_list[0]
    unit_list2 = unit_list[1:]
    max_cnt = goal // unit

    return [[i] + s for i in range(max_cnt + 1) \
                    for s in coin_combos(goal - i * unit, unit_list2)]

Here's a sample invocation, using the parameters you gave. It seems to find the correct number of solutions:

>>> r = coin_combos(500, [500, 200, 100, 50, 20, 10])
>>> len(r)
451
>>>

Coins all combinations - strange difference between 2 algorithms

2 Answers2