неожиданное поведение в этой программе в python

Question

У меня есть этот код для вычисления минимального количества монет из суммы с данным списком деноминаций. для например: 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]) 

Программа, кажется, работает хорошо, когда я закомментировать либо из операторов печати в основном. , когда у меня есть оба вызова функций, он печатает неправильно. закомментируйте или распечатывайте заявления в основном, и вы увидите, что он правильно печатает минимальные монеты.

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] 

Answer 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) 

проходят в отдельном кэше для каждого набора номиналов

Проблема заключается в том, что кэш уже знает, как внести изменения в 7, как 5,1,1, так он просто возвращает это. .. кэш не знает, что 5 больше не в наборе деноминации ...

словари изменчивы, как списки ... это должно продемонстрировать проблему

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

dict_fn() 
dict_fn()