Разбивая int на сумму

Question

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

У меня возникла проблема с моей проблемой, и я интересно, есть ли у вас какие-либо советы / подсказки. По сути, у меня есть переменная (int), которую я хочу разбить на добавление заданного числа терминов. И, поскольку это было слишком просто, эти термины должны быть выбраны из множества возможных терминов. (Допустим, здесь есть хотя бы один способ сделать это, проверки были бы выполнены раньше). Позвольте мне проиллюстрировать:

var = 12
nbr_terms = 3
possible_terms = [2, 3, 4, 6]
# Function to create
breaker(var, nbr_terms, possible_terms)

Функция breaker() должна возвращать (одно из) разложение. Например, здесь это может быть 6+3+3 или 4+4+4.

У меня есть идея, которая, я думаю, могла бы работать, просто она могла бы стать чрезвычайно ресурсоемкой, если бы массив possible_terms имел много элементы. Через этот массив l oop можно было бы проверить каждую возможную комбинацию из заданного числа терминов, сохранить каждую рабочую комбинацию в другом массиве и выбрать ее случайным образом. Кроме того, поскольку nbr_terms также является параметром, я не знаю, как поступить.

Answer 1

Я нашел способ сделать это рекурсивно. Функция находит все возможные комбинации (2+4+6 отличается от 4+2+6 для этой функции) и возвращает список, затем я выбираю одну из них случайным образом.

Вот функция:

def broker(var, nbr_terms, possible_terms, list_all, nbr, term, current_list):
    if(term == nbr_terms and nbr == var):
        list_all.append(current_list)
    elif(nbr < var and term < nbr_terms):
        for i in possible_terms:
            broker(var, nbr_terms, possible_terms, list_all, nbr+i, term+1, current_list+[i])

Позвольте мне объяснить аргументы: var, nbr_terms и possible_terms такие же, как в вопросе, list_all - список рабочих комбинаций, а nbr, term и current_list - это рекурсивные аргументы

Answer 2

Я думаю, combinations_with_replacement из itertools - это то, что вам нужно. Таким образом, он выдаст все комбинации possible_terms без замены, и вы можете назначить номер элемента в каждой комбинации (в вашем случае это nbr_terms). Должны работать следующие коды:

import itertools as it
def breaker(var, nbr_terms, possible_terms):
    results=[]
    for i in it.combinations_with_replacement(possible_terms, nbr_terms):
       # print (i, sum(i))
        if sum(i)==var:
            results.append(i)
    return results

Я запустил его с указанными вами числами:

var = 12
nbr_terms = 3
possible_terms = [2, 3, 4, 6]
breaker(var, nbr_terms, possible_terms)

Возвращает список со всеми тремя возможными комбинациями, которые составляют до 12:

[(2, 4, 6), (3, 3, 6), (4, 4, 4)]