递归树过早终止函数 [英] Recursive tree terminates function prematurely

问题描述

我正在尝试定义一个函数，该函数返回等于给定总和的所有合法硬币组合的列表.假设给定的金额是 10，而法定硬币是 5, 2, 3.在这种情况下，函数应该返回:

I am trying to define a function that returns a list of all combinations of legal coins that amount to a given sum. Let's say the given sum were 10 and the legal coins were 5, 2, 3. In that case the function should return:

[[2, 2, 2, 2, 2], [3, 3, 2, 2], [5, 3, 2], [5, 5]]

我已经设法创建了一个递归函数，它给了我正确的结果，但是通过在单独的行上打印正确的答案并混合一堆None.

I've managed to create a recursive function that gives me the correct result, but by printing the correct answers on separate lines and mixing in a bunch of None's.

如何在不提前终止函数的情况下返回合法解决方案列表的正确答案.我知道我的功能是无效的.我可以自己想到一些改进，稍后会实施.

How can I return the correct answer to a list of legal solutions without terminating the function prematurely. I know that my function is ineffective. I can think of some improvements myself, and will implement them later.

这是我的代码:

def count_change(tot_amount, coins, used_coins=[]):

    # Sort coins and get rid of coins that are too big
    if len(used_coins) == 0:
        coins = [x for x in sorted(coins) if x <= tot_amount]

    for coin in coins:
        # If the first condition holds I want to add the printed
        # statement to a list of solution instead of printing
        if tot_amount - sum(used_coins) == coin:
            print(used_coins + [coin])
        elif tot_amount - sum(used_coins) > coin:
            print(count_change(tot_amount,
                               [x for x in coins if x <= coin],
                               used_coins + [coin]))

print(count_change(10, [5, 2, 3]))

这是输出:

[2, 2, 2, 2, 2]
None
None
None
None
None
None
None
[3, 3, 2, 2]
None
None
None
None
None
None
[5, 3, 2]
None
[5, 5]
None
None

推荐答案

你只需要把你的函数变成一个 generator，将那些 print 调用替换为 yield.

You just need to turn your function into a generator, by replacing those print calls with yield.

我还将 used_coins 的默认值更改为 None，因为您真的不想要这里的默认可变参数.有关详细信息，请参阅最小惊讶"和可变默认参数.

I've also changed the default of used_coins to None, since you don't really want a default mutable argument here. See "Least Astonishment" and the Mutable Default Argument for details.

def count_change(tot_amount, coins, used_coins=None):
    # Sort coins and get rid of coins that are too big
    if used_coins is None:
        used_coins = []
        coins = [x for x in sorted(coins) if x <= tot_amount]

    for coin in coins:
        # If the first condition holds we have a valid combination 
        if tot_amount - sum(used_coins) == coin:
            yield used_coins + [coin]
        # Otherwise, if this coin is small enough, recurse to find combinations
        # that use this coin in addition to the existing used_coins
        elif tot_amount - sum(used_coins) > coin:
            yield from count_change(tot_amount,
                               [x for x in coins if x <= coin],
                               used_coins + [coin])

for t in count_change(10, [5, 2, 3]):
    print(t)

输出

[2, 2, 2, 2, 2]
[3, 3, 2, 2]
[5, 3, 2]
[5, 5]

<小时>

如果您确实需要一个解决方案列表，那么只需将生成器运行到一个列表中，如下所示:

---

If you do actually need a list of the solutions, then simply run the generator into a list, like this:

seq = list(count_change(10, [5, 2, 3]))
print(seq)

输出

[[2, 2, 2, 2, 2], [3, 3, 2, 2], [5, 3, 2], [5, 5]]

这篇关于递归树过早终止函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！