Как собрать результаты рекурсивного отслеживания?

Question

Я учу себя рекурсивному возвращению.Для задачи суммирования кубиков я не могу понять, как элегантно собрать результаты.

Для справки вот мой код, который просто печатает любой бросок кубика, который соответствует критериям.В идеале я хочу изменить его, чтобы вместо вывода результата я мог составить список выбранных кубиков и вернуть его.

Ниже приведен код, который не выполняет то, что я хочу

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 для возврата результатов из ваших функций:

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

Для заявленной цели элегантность я хотел бы пойти с более простой конструкцией без вспомогательной функции и без дополнительных аргументов:

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 3

Вы можете передать список «результатов», в котором можно сохранить результаты:

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

Обратите внимание, что будет возвращено много дубликатов, если порядок не имеет значения. Возможно, вы захотите исследовать изменение этого параметра, чтобы вычислять меньшую целевую сумму при каждой рекурсии, и запоминать это каким-то образом, чтобы сэкономить на большой работе. Смотрите также, например, Рассчитать количество способов бросить определенное число