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

Question

В python 3 Я пытаюсь написать функцию, которая принимает два натуральных числа ? и ? в качестве входных данных и возвращает набор всех кортежей размером ?, сумма которых равна ?.

Я построил следующие функции:

def get_tuples(length, total):
    if length == 1:
        yield (total,)
        return


    for i in range(total + 1):
        for t in get_tuples(length - 1, total - i):
            yield (i,) + t

, который, например, list (get_tuples (2, 8)) возвращает правильные результаты, и:

 def get_tuples(length, total):
    if length == 1:
        return [(total,)]

    comp = []
    for i in range(total + 1):
        for t in get_tuples(length - 1, total - i):
            comp.append((i,) + t)
        return comp

, который, однако, возвращает неправильный результат (т.е. один кортеж). Кто-нибудь может объяснить, почему и как исправить вторую функцию?

Answer 1

Просто поместите отступ на один отступ:

def get_tuples(length, total):
    if length == 1:
        return [(total,)]

    comp = []
    for i in range(total + 1):
        for t in get_tuples(length - 1, total - i):
            comp.append((i,) + t)
    return comp

Изменить: убедитесь, что вы понимаете, почему

Answer 2

Здесь вы go:

def get_tuples(length, total):
if length == 1:
    return [(total,)]

comp = []

for i in range(total + 1):
    for t in get_tuples(length - 1, total - i):
        comp.append((i,) + t)
return comp

Выньте оператор возврата из l oop.

Answer 3

Ответ

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

Однако, если вам интересно, как избавиться от рекурсии и сделать код быстрее в то же время, вот решение:

def get_tuples_optimized(length, total):
    comp = []

    # Stack of partial tuples to process, initialized with an empty tuple
    todo = [(total, tuple())]

    # Loop as long as we have partial tuples on our stack
    while todo:
        # Take the next partial tuple
        amount_left, partial_tuple = todo.pop()

        if len(partial_tuple) == length - 1:
            # Put all that is left as the last element
            comp.append(partial_tuple + (amount_left,))
        else:
            # Add all possible extensions-by-one to our stack
            for i in range(amount_left + 1):
                extended_tuple = partial_tuple + (i,)
                todo.append((amount_left - i, extended_tuple))

    return comp