unexpected behaviour in this program in python

问题:

I have this code to calculate minimum number of coins from a sum with given list of denomiations. for eg : minimum change for 69 with denomiations [25,10,5,1] : [25, 25, 10, 5, 1, 1, 1, 1]

def get_min_coin_configuration(sum=None, coins=None, cache={}):
    #if cache == None:  # this is quite crucial if its in the definition its presistent ...
    #    cache = {}
    if sum in cache:
        return cache[sum]
    elif sum in coins:  # if sum in coins, nothing to do but return.
        cache[sum] = [sum]
        return cache[sum]
    elif min(coins) > sum:  # if the largest coin is greater then the sum, there's nothing we can do.
        #cache[sum] = []
        #return cache[sum]
        return []
    else:  # check for each coin, keep track of the minimun configuration, then return it.
        min_length = 0
        min_configuration = []
        for coin in coins:
            results = get_min_coin_configuration(sum - coin, coins, cache)
            if results != []:
                if min_length == 0 or (1 + len(results)) < len(min_configuration):
                    #print "min config", min_configuration
                    min_configuration = [coin] + results
                    #print "min config", min_configuration
                    min_length = len(min_configuration)
                    cache[sum] = min_configuration
        return cache[sum]
if __name__ == "__main__":
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1])
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1])

The program seems to work fine when I comment out either of the print statements in the main. when I have both function calls, it is printing wrongly. comment out either print statements in the main and you would see that it prints the minimum coins correctly.

minimum change for 69 with denomiations [25,10,5,1] by recursive :  [25, 25, 10, 5, 1, 1, 1, 1]
*********************************************
minimum change for 7 with denomiations [4,3,1] by recursive :  [5, 1, 1]

回答1:

if __name__ == "__main__":
    cache_denom_set1 = {}
    cache_denom_set2 = {}
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1],cache_denom_set1)
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1],cache_denom_set2)

pass in a separate cache for each set of denominations

the problem is that your cache already knows how to make change for 7 as 5,1,1 so it just returns that ... the cache is unaware that 5 is no longer in the denomination set ...

dictionaries are mutable like lists ... this should demonstrate the problem

def dict_fn(cache={}):
    cache[len(cache.keys())] = 1
    print cache

dict_fn()
dict_fn()