如何收集递归回溯的结果？

Question

我正在自学递归回溯。对于骰子求和问题，我不知道如何优雅地收集结果。

作为参考，这里是我的代码，它只打印符合条件的任何骰子。理想情况下，我想更改它，而不是打印输出，我可以建立一个包含那些选择的骰子的列表，然后 return 它。

下面的代码不符合我的要求

def dice_sum(num_dice: int, target_sum: int) -> None:
    dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
    if num_dice == 0 and sum(chosen) == target_sum:
        print(chosen)
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            dice_sum_helper(num_dice - 1, target_sum, chosen)
            chosen.pop()

相反，我希望它做这样的事情

from typing import List
DiceResult = List[List[int]]


def dice_sum(num_dice: int, target_sum: int) -> DiceResult:
    return dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> DiceResult:
    if num_dice == 0 and sum(chosen) == target_sum:
        # Return the value that meets the constraints
        return chosen
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            # Return the result of my recursive call and build the list of lists?
            result = dice_sum_helper(num_dice - 1, target_sum, chosen)
            return result.append(result)
            # End of that logic
            chosen.pop()

与确切的代码相比，我更多地是在寻找要使用的理论或模式。如果不使用外部列表，我无法完全获取代码来收集和附加每个结果。

Answer 1

您可以利用 yield 和 yield from 从您的函数中得到 return 结果：

from typing import List

def dice_sum(num_dice: int, target_sum: int) -> None:
    yield from dice_sum_helper(num_dice, target_sum, [])


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int]) -> None:
    if num_dice == 0 and sum(chosen) == target_sum:
        yield chosen[:]
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            yield from dice_sum_helper(num_dice - 1, target_sum, chosen)
            chosen.pop()

# you can store the results e.g. to list: 
# results = list(dice_sum(3, 12))

for dices in dice_sum(3, 12):
    for d in dices:
        print('{: ^4}'.format(d), end='|')
    print()

打印：

 1  | 5  | 6  |
 1  | 6  | 5  |
 2  | 4  | 6  |
 2  | 5  | 5  |
 2  | 6  | 4  |
 3  | 3  | 6  |
 3  | 4  | 5  |
 3  | 5  | 4  |
 3  | 6  | 3  |
 4  | 2  | 6  |
 4  | 3  | 5  |
 4  | 4  | 4  |
 4  | 5  | 3  |
 4  | 6  | 2  |
 5  | 1  | 6  |
 5  | 2  | 5  |
 5  | 3  | 4  |
 5  | 4  | 3  |
 5  | 5  | 2  |
 5  | 6  | 1  |
 6  | 1  | 5  |
 6  | 2  | 4  |
 6  | 3  | 3  |
 6  | 4  | 2  |
 6  | 5  | 1  |

Answer 2

您可以传递一个 'results' 列表来存储结果：

from typing import List
DiceResult = List[List[int]]


def dice_sum(num_dice: int, target_sum: int) -> DiceResult:
    results = []
    dice_sum_helper(num_dice, target_sum, [], results)
    return results


def dice_sum_helper(num_dice: int, target_sum: int, chosen: List[int], results: DiceResult):
    if num_dice == 0 and sum(chosen) == target_sum:
        # Store the value that meets the constraints
        results.append(chosen.copy())
    elif num_dice == 0:
        pass
    else:
        for i in range(1, 7):
            chosen.append(i)
            dice_sum_helper(num_dice - 1, target_sum, chosen, results)
            chosen.pop()

请注意，如果顺序无关紧要，这将返回许多重复项。您可能想研究更改此设置以在每次递归时计算更小的目标总和，并以某种方式记住它以节省大量工作。另见例如Calculate the number of ways to roll a certain number

Answer 3

为了优雅的既定目标，我会选择更简单的设计，不使用辅助函数也不传递额外参数：

def dice_sum(num_dice, target_sum):
    solutions = []

    for i in range(1, 7):
        if target_sum < i:
            continue

        if target_sum == i:
            if num_dice == 1:
                solutions.append([i])

            continue

        for solution in dice_sum(num_dice - 1, target_sum - i):
            solutions.append([i] + solution)

    return solutions

print(dice_sum(3, 5))

输出

> python3 test.py
[[1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1]]
>

为了提高效率，您可以添加：

if target_sum - i < num_dice - 1:
            continue

在内部 for 循环之前避免递归，如果没有希望的话。

Answer 4

具有提前中止条件的递归生成器，因此关于掷骰子的顺序，您不会得到重复的解决方案。 IE。我假设您的骰子无法识别，因此数字的顺序无关紧要。

def dice_sum (num_dice, target_sum, start=1):
    if num_dice == 1 and 0 < target_sum < 7:
        yield (target_sum, )
        return
    if num_dice * 6 < target_sum or num_dice > target_sum:
        return
    for i in xrange(start, 7):
        for option in dice_sum(num_dice - 1, target_sum - i, i):
            if i > option[0]:
                return
            yield (i, ) + option

>>> tuple(dice_sum(3, 12))
((1, 5, 6), (2, 4, 6), (2, 5, 5), (3, 3, 6), (3, 4, 5), (4, 4, 4))

如何收集递归回溯的结果？

How to collect results of recursive backtracking?

python

recursion

backtracking

recursive-backtracking