计算变化的Baktracking功能超出了最大递归深度 [英] Baktracking function which calculates change exceeds maximum recursion depth

问题描述

我正在尝试编写一个函数，该函数查找产生指定数量的硬币的所有可能组合，例如，它计算从面额1p，2p，5p清单中更改2英镑的所有可能方式，10p，20p，50p，1磅，2磅.我对此一无所知，找不到正确的解决方案.

I'm trying to write a function that finds all possible combinations of coins that yield a specified amount, for example it calculates all possible way to give change for the amount 2 British pounds from the list of denominations 1p, 2p, 5p,10p,20p,50p,1pound,2pound. I'm stuck with this and can't find the right solution.

我希望main函数是递归的，因为我想更好地理解递归.该算法必须回溯，如果某个时候发现的组合超过了要匹配的数量，则程序应返回到先前的步骤并从不同的点开始.

I want the main function to be recursive, because I want to understand recursion better. The algorithm must backtrack, if the combination found at some moment exceeds the amount which is to be matched the program should return to previous steps and start from different point.

到目前为止，我已经编写了一个普通的(不是递归的)函数，如果每个硬币只使用一次，它会计算给定国家/地区中所有硬币的可能组合(这很简单).我还没有尝试找到给定总和的正确组合，只是所有可能的硬币组合.

Thus far I've written a normal (not recursive) function that computes all possible combinations of coins in a given country if each coin is used only once (this is fairly straightforward). I am not trying to find the right combination for a given sum yet, just all possible combinations of coins.

def calcCoins(coins):
    """ 
    returns all possible combinations of coins, when called with 
    [1,2,5,10,20,50,100,200] returns a list of 126 Counters containing 
    for instance Counter{1:1}, Counter{1:1,2:1,5:1}, Counter {50:1,100:1} etc
    """
    i,combs = 1, []
    while i < len(coins):
        for x in combinations(coins,i):
            combs.append(Counter(x))
        i += 1
    return combs

现在，我有一个笨拙的递归函数，该函数接受组合和所需的数量作为参数，并返回所有可能的方式来给出等于该数量的更改.

Now I have a clumsy recursive function that accepts a combination and desired amount as arguments and returns all possible ways in which a change equal to this amount can be given.

def findSum(comb,goal,rightOnes):
    if rightOnes == None:
        rightOnes = []
    if sum(comb.elements()) == goal:
        comb_ = Counter(comb)
        if comb_ in rightOnes:
             # probably a cycle, return combinations gathered and exit
             return rightOnes
        rightOnes.append(comb_)
    elif sum(comb.elements()) > goal:
        #this is meant to be backtracking
        return False
    for k in comb:
        comb[k] += 1
        if findSum(comb,goal,rightOnes) != False:
            return findSum(comb,goal,rightOnes)
        else:
            comb[k] = 1
    return rightOnes

对于很小的组合，该函数可以运行并正确返回: 例如

The function runs and returns correctly for very small combinations: e.g. for

test2 = Counter({10: 1, 20: 1})
findSum(test2,200,[])

它返回:

 [Counter({10: 18, 20: 1}), Counter({10: 16, 20: 2}), 
  Counter({10: 14, 20: 3}), Counter({10: 12, 20: 4}), 
  Counter({10: 10, 20: 5}), Counter({10: 8, 20: 6}), 
  Counter({20: 7, 10: 6}), Counter({20: 8, 10: 4}), 
  Counter({20: 9, 10: 2})]

但对于较大的变量，例如

But for larger ones, such as

test3 = Counter({1: 1, 2: 1, 10: 1})
test4 = Counter({1: 1, 2: 1, 100: 1, 10: 1}) 

它超过了递归的限制.它运行良好，直到一会儿，打印出部分结果，但在某个时候，它超过了最大递归深度.

it exceeds the limit of recursion. It runs fine until some moment, prints out partial results but then at some point it exceeds maximum recursion depth.

我犯了什么错误，导致该函数无法运行?我执行回溯功能吗?我会省略一些情况吗?如何优化此功能，使其不超过最大递归深度?

What are the mistakes I'm making which cuase this function to run amok? Is it something with my implementation of backtracking? Am I omitting some case? How to optimize this function so that it does not exceed maxim recursion depth?

提前谢谢！

这是回溯:

   if findSum(comb,goal,rightOnes) != False:
   File "C:\playground\python\problem31.py", line 105, in findSum
   if sum(comb.elements()) == goal:
   File "C:\Python27\lib\collections.py", line 459, in elements
   return _chain.from_iterable(_starmap(_repeat, self.iteritems()))
   RuntimeError: maximum recursion depth exceeded while calling a Python object

和最后一个部分结果，就在函数中断之前(用test3调用)

and the last partial result, just before the break of the function (called with test3)

[Counter({1: 163, 2: 1, 20: 1, 10: 1, 5: 1}), Counter({1: 161, 2: 2, 20: 1, 10: 1, 5: 1}), 
 Counter({1: 159, 2: 3, 20: 1, 10: 1, 5: 1}), Counter({1: 157, 2: 4, 20: 1, 10: 1, 5: 1}), 
 Counter({1: 155, 2: 5, 20: 1, 10: 1, 5: 1}), Counter({1: 153, 2: 6, 20: 1, 10: 1, 5: 1})]

推荐答案

首先，作为这个问题表明，由于Python作为一种语言的语义，递归并不是一种特别有效的范例.但是，如此处指出的那样，可以使用sys.setrecursionlimit(2000). (或者无论您需要多少)，我想强调一下这是懒惰"的解决方案，我强烈建议您使用第一个(非递归)版本.

First of all, as the first answer to this question shows, because of the semantics of Python as a language, recursion isn't a particularly efficient paradigm. However, as is pointed out there, it is possible to use sys.setrecursionlimit(2000). (Or however much you need) I want to stress that this is the "lazy" solution, I strongly recommend using your first (non-recursive) version instead.

这篇关于计算变化的Baktracking功能超出了最大递归深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！