Python - Changing to Memoization

Question

I've coded a function that finds all changes of n using the given coins when order makes a change.

def find_change(n, coins):
    if n < 0:
        return []

    if n == 0:
        return [[]]

    all_changes = []

    for last_used_coin in coins:
        curr_changes = find_change(n - last_used_coin, coins)

        for change in curr_changes:
            change.append(last_used_coin)

        all_changes.extend(curr_changes)

    return all_changes

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

The code above is "normal" and now I want to code it again but as a memo. The values that will be saved in the memo are mutable therefore I should use deepcopy but I don't know how to use it. Can someone show me how?

EDIT: idea how to use deepcopy:

from copy import deepcopy
lst1 =[[1], [2]]
lst 2 = deepcopy(lst1)
print lst

and we get:

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

Your code does not execute, please post a working version of this function. For starters, find_changes is a typo, but the function does not complete execution. Please also post a working example of using the function. — Peter Gibson
– Peter Gibson, Commented Jan 20, 2014 at 1:41

Blender · Accepted Answer · 2014-01-20 02:35:21Z

2

Your only changing argument is n, so just use it as the key for your lookup table:

if n not in cache:
    ...

You could even turn it into a decorator:

def memoized(function):
    cache = {}

    def inner(n, coins):
        if n not in cache:
            cache[n] = function(n, coins)

        return cache[n]

    return inner

@memoized
def find_change(n, coins):
    ...

edited Jan 20, 2014 at 2:35

answered Jan 20, 2014 at 2:29

Blender

300k55 gold badges462 silver badges512 bronze badges

Sign up to request clarification or add additional context in comments.

18 Comments

user3210483 Over a year ago

First of all, thank you very much. But, I would really want to use deepcopy, I tried to undertstand how it works and how to make this code in memo but I had no success. I would really like if you could try to do this way. Thanks again.

Blender Over a year ago

@user3210483: Using deepcopy won't make your list immutable. Your list doesn't change in the first place, so why use it as the key for a lookup table? The only thing that changes is n.

user3210483 Over a year ago

I have an idea how to try to use deepcopy, please look at my edit in the first message. thanks.

Blender Over a year ago

@user3210483: Change cache[n] = function(n, coins) to cache[n] = deepcopy(function(n, coins)) and I guess

Peter Gibson Over a year ago

Perhaps coins is supposed to change? This would make sense given the desire to use deepcopy. @user3210483 Are you selecting change from a limited set of coins?

|

Collectives™ on Stack Overflow

Python - Changing to Memoization

1 Answer 1

18 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

18 Comments

Your Answer

Sign up or log in

Post as a guest

Related