CODEWITHSUNDEEP
pythonalgorithmdictionarydynamic-programming
random
random

Reputation: 19

Unintended changes in dictionary's content when solving the coin change problem

The problem I was trying to solve was: given a list of coins and a sum, find out all the possible ways to form the sum using those coins (you can use one coin infinite amount of time) For example: 4 and [1,2,3] will give the answer [1,1,1,1], [1,1,2], [2,2], [1,3] (here, there are three types of coins, those with value of 1, 2 and 3). Here is my attempt of the problem:

def coin_check(target_sum, numbers):
    memo = {}

    def helper(target_sum, numbers):
        if target_sum == 0:
            return [[0]]
        if target_sum in memo:
            return memo[target_sum]
        memo[target_sum] = []
        for num in numbers:
            remainder = target_sum - num
            if remainder >= 0:
                combination = helper(remainder, numbers)
                if combination != []:
                    for i in combination:
                        i.append(num)
                        memo[target_sum].append(i)
        print(memo)
        return memo[target_sum]
    return helper(target_sum, numbers)
print(coin_check(4,[1,2,3]))

Here I try to use dynamic programming to keep track of which value I have already tried. The answer I got was:

[[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 
2, 1, 1, 2, 3]]

which is of course incorrect. The evolution of the memo after the the program has run was:

{4: [], 3: [], 2: [], 1: [[0, 1]]}
{4: [], 3: [], 2: [[0, 1, 1], [0, 2]], 1: [[0, 1, 1]]}
{4: [], 3: [[0, 1, 1, 1, 2], [0, 2, 1], [0, 1, 1, 1, 2], [0, 3]], 2: [[0, 1, 1, 1, 2], [0, 2, 1]], 1: [[0, 1, 1, 1, 2]]}
{4: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3]], 3: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1]], 2: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2]], 1: [[0, 1, 1, 1, 2, 1, 1, 2, 3]]}

This puzzles me because I can't see where in my program did I say to change the value of memo[1] into [0,1,1] afterward [0,1] has already existed. Can someone please explain to me why this is happening, thank you.

P.s: here, my algorithm always puts 0 in each possible combination.

Upvotes: 0

Views: 123

Answers (2)

Manby
Manby

Reputation: 454

In line 16 of your snippet, when you append num to each possible remainder combination, you are actually directly changing the lists stored in memo.

This happens because in python, when you grab a list and store it in a variable, that variable actually holds a pointer to that list's address in memory, rather than a copy of the list.

This can be demonstrated by executing:

a = [1, 2]
b = a
b.append(3)
print(a)

You will notice that the output is [1, 2, 3], because b actually contains a pointer to the list, rather than a copy of it. There is still only one list in memory.

A useful check is to evaluate the lists by using is. If aand b point to the same list in memory, then

a is b

will evaluate to True. It is important to understand that is and == are not the same operator.

Going back to the problem, this means that whenever i is altered, the entry in memo is altered too, because combination is actually a list of pointers to lists in memo. This is clearly something you want to avoid.

Instead, before appending num to i, copy i into a new, detached list using i.copy() to prevent the actual data in memo from being changed.

Instead of:

for i in combination:
    i.append(num)
    memo[target_sum].append(i)

Try:

for i in combination:
    j = i.copy()
    j.append(num)
    memo[target_sum].append(j)

Upvotes: 0

trincot
trincot

Reputation: 350137

The main issue is this line:

i.append(num)

This mutates a list that was potentially already put in memo in the deeper recursive call. You should create a new list instead:

memo[target_sum].append(i + [num])

There are also the following issues:

  • The following code...

    return [[0]]

    ... will make that every combination will include the value 0, since they are all built by extending this base case. You should instead do:

    return [[]]

  • With this code...

    for num in numbers:
    remainder = target_sum - num

    ... you are reducing remainder in a accumulative way, i.e. you don't undo the change to remainder at the end of an iteration of the loop. Instead, don't use this variable at all, and keep the reduced expression dynamic:

    for num in numbers:
    if target_sum >= num:
        combination = helper(target_sum - num, numbers)

With these corrections you'll already get a more reasonable result.

There is just one more thing missing: all permutations of a solution are also included. As you want those excluded, you'll need to tell the recursive call from which coin onwards coins may be selected. This requires a bit more changes, but it could look like this:

def coin_check(target_sum, numbers):
    memo = {}

    def helper(target_sum, mincoin):
        if target_sum == 0:
            return [[]]
        if target_sum in memo:
            # get memo, but only return combis that obey mincoin restriction
            return [row for row in memo[target_sum] if row[0] >= mincoin]
        memo[target_sum] = []
        for coinid in range(mincoin, len(numbers)):
            num = numbers[coinid]
            if target_sum >= num:
                combination = helper(target_sum - num, coinid)
                if combination != []:
                    for combi in combination:
                        # prefix with coinid
                        memo[target_sum].append([coinid] + combi)
        return memo[target_sum]
    
    # Convert coin id to coin value
    return [
        [numbers[coinid] for coinid in combi] 
            for combi in helper(target_sum, 0)
    ]


print(coin_check(4, [1, 2, 3]))

Upvotes: 2

Related Questions