CODEWITHSUNDEEP
pythondivide-and-conquercoin-change
pweave
pweave

Reputation: 43

Divide and conquer recursive solution for making change

I'm trying to implement a divide and conquer program that when given a coin set c = {c0, c1,...,cn} and an amount A, it finds how many different ways A can be paid, as well as how many times the function was recursed through.

My thought is to do something like this:

callsMade = 0
coins = [1,5,10,25]

def makeChange(A, c):
    global callsMade
    callsMade += 1
    if(A == 0):
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i in range(len(coins)):
        combos += makeChange(A - coins[i], i)
    return combos

Where A is the amount being passed in and c = len(coins)-1. Though, this snippet of code doesn't behave as I expect it to. My thought process is to loop through the array of coins, subtracting the current amount by the coin in that position of the array and recursively call the makeChange function with the lower amount and next coin in the array, then increment the global callsMade by 1 each time.

Using the coinset = [1,5,10,25] and amount A = 200, the amount of combinations should be 1463 with around 1500 calls made.

Upvotes: 1

Views: 640

Answers (2)

Mark
Mark

Reputation: 92440

The basic idea is right, but you need to consider some issues with the recursion and what you want to count as a correct answer.

If you start simply, you can ask how many combinations of [1,5,10,25] should equal 6:

Should it be 3:
[1, 1, 1, 1, 1, 1], [5, 1], [1, 5]?
or 2:
[1, 1, 1, 1, 1, 1], [1, 5]?

Two makes the most sense to me. To do this you need to pass a subset of your coins array back to the recursion so when you are in the for loop looking at 5 you don't consider [5, 1] again — presumable you've already counted [1, 5] at this point. Instead of passing the unused c parameter, pass in a coins list. Then manage that list in the loop. Here I've added an extra parameter cur to collect the combinations just to help check the work. You don't need that if you just want the count.

def makeChange(A, coins, cur = None):
    ''' This will also collect the combinations to check the work'''
    if cur is None:
        cur = []
    global callsMade
    callsMade += 1
    if(A == 0):
        print(cur)
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i, coin in enumerate(coins):
        if coin > A: # don't bother if coin is too big
            continue
        # pass a subset of the list into recursion
        combos += makeChange(A - coin, coins[i:], cur + [coin])
    return combos

coinset = [1,5,10,25]
A = 10
makeChange(A, coinset)

Result:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 5]
[5, 5]
[10]
Out[456]:
4

Setting A to 200 shows 1463 combinations.

Upvotes: 0

tobias_k
tobias_k

Reputation: 82899

The recurrence relation looks something like this (I removed the calls counter for brevity):

def makeChange(A, coins, k=0):
    if A == 0: return 1
    if A <  0: return 0
    return sum(makeChange(A - coins[i], coins, i) for i in range(k, len(coins)))

I.e., you do not consider coins that are smaller than those you have already taken, otherwise you will get combination like [1, 1, 5] and [1, 5, 1] and so on. With this, I get 1463 combinations for makeChange(200, (1,5,10,25)) with a total of 111491 calls -- a bit more than what you expected.

Note that this function will calculate many combinations more than once. E.g., you can reach A=194 by [1,5] or by [1,1,1,1,1,1], and so on, but the result for makeChange(194, coins, k=1) is the same for both ways. You can use functools.lru_cache to automatically memoize those values. This way, you get the same result after just 801 calls.

@functools.lru_cache(None)
def makeChange(A, coins, k=0):
    # same as above

(For memoization, you have to include the coins as a parameter (as a tuple, not a list, in order to be hashable), otherwise it would reuse the result for a different set of coins.)

Upvotes: 1

Related Questions