Учитывая список чисел, сколько разных способов вы можете сложить их вместе, чтобы получить сумму S?

Question

Учитывая список чисел, сколько разных способов вы можете сложить их вместе, чтобы получить сумму S?

Пример:

list = [1, 2]

S = 5

1) 1 + 1 + 1 + 1 + 1 = 5

2) 1 + 1 + 1 + 2= 5

3) 1 + 2 + 2 = 5

4) 2 + 1 + 1 + 1 = 5

5) 2 + 2 + 1 = 5

6) 1 + 2 + 1 + 1 = 5

7) 1 + 1 + 2 + 1 = 5

8) 2 + 1 + 2 = 5

Answer = 8

Это то, что я пробовал, но в качестве ответа выдается только 3

lst = [1, 2]
i = 1
result = 0
while i <= 5:
    s_list = [sum(comb) for comb in combinations_with_replacement(lst, i)]
    for val in s_list:
        if val == 5:
            result += 1
    i+= 1

print(result)

Однако, это выводит три.Я считаю, что он выдает три, потому что он не учитывает другой порядок, в котором вы можете добавить числа. Любые идеи о том, как решить эту проблему.

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

Answer 1

Использование Динамическое программирование .

Мы предполагаем, что ваш список состоит из [1,2,5], поэтому у нас есть эта рекурсивная функция:

f(n,[1,2,5]) = f(n-1,[1,2,5]) + f(n-2,[1,2,5]) + f(n-5,[1,2,5])

Потому что если первое число в сумме равно 1, то у вас есть f(n-1,[1,2,5]) опции для остальных, а если это 2, у вас есть f(n-2,[1,2,5]) опции для остальных и так далее ...

поэтому начните с f(1) и продолжайте работать с динамическим программированием.в худшем случае это решение O(n^2), и это происходит, когда в вашем списке есть O(n) элементов.

Решение будет выглядеть примерно так:

answers = []
lst = [1,2]
number = 5
def f(target):
  val = 0
  for i in lst:               #O(lst.count())
    current = target - i
    if current > 0:
      val += answers[current-1]
  if lst.__contains__(target): #O(lst.count())
    val += 1
  answers.insert(target,val)

j = 1;
while j<=number:  #O(n) for while loop
  f(j)
  j+=1

print(answers[number-1])

здесь это рабочая версия.

Answer 2

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

def cal(target, choices, record):

    min_choice = min(choices)
    if min_choice > target:
        return False

    for i in range(0, target+1):
        if i == 0:
            record.append(1)
        elif i < min_choice:
            record.append(0)
        elif i == min_choice:
            record.append(1)
        else:
            num_solution = 0
            j = 0
            while j < len(choices) and i-choices[j] >= 0:
                num_solution += record[i-choices[j]]
                j += 1
            record.append(num_solution)


choices = [1, 2]
record = []
cal(5, choices, record)
print(record)
print(f"Answer:{record[-1]}")

Основная идея здесь заключается в использовании дополнительного массива record для записи того, сколько способов можно найти для получения текущего num, например, record[2] = 2 означает, что мы можем использовать способы получения суммы 2 (1+1 или 2).

И у нас есть record[target] = sum(record[target-choices[i]]), где i перебирает варианты.Попытайтесь думать, что способ получения sum=5 должен быть связан со способом получения sum=4 и т. Д.

Answer 3

Использование itertools.combinations_with_replacement и permutations:

import itertools

l = [1,2]
s = 5

res = []
for i in range(1, s+1):
    for tup in itertools.combinations_with_replacement(l, i):
        if sum(tup) == s:
            res.extend(list(itertools.permutations(tup, i)))
res = list(set(res))

print(res)
[(1, 2, 2),
 (2, 2, 1),
 (1, 1, 2, 1),
 (1, 2, 1, 1),
 (2, 1, 1, 1),
 (1, 1, 1, 2),
 (2, 1, 2),
 (1, 1, 1, 1, 1)]

print(len(res))
# 8

Answer 4

Комбинации с элементами в другом порядке считаются эквивалентными.Например, № 3 и № 5 из вашего списка сумм считаются эквивалентными, если вы говорите только о комбинациях.

Напротив, перестановки считают две коллекции уникальными, если они состоят из одинаковых элементов в разныхзаказ.

Чтобы получить искомый ответ, вам необходимо объединить оба понятия.

1. Сначала воспользуйтесь своей техникой, чтобы найти комбинации, соответствующие вашим критериям
2. Затем переставьте набор чисел из комбинации
3. Наконец, соберите сгенерированные перестановки в наборе для удаления дубликатов.

[ins] In [01]: def combination_generator(numbers, k, target):
          ...:     assert k > 0, "Must be a positive number; 'k = {}".format(k)
          ...:     assert len(numbers) > 0, "List of numbers must have at least one element"
          ...:
          ...:     for candidate in (
          ...:         {'numbers': combination, 'sum': sum(combination)}
          ...:         for num_elements in range(1, k + 1)
          ...:         for combination in itertools.combinations_with_replacement(numbers, num_elements)
          ...:     ):
          ...:         if candidate['sum'] != target:
          ...:             continue
          ...:         for permuted_candidate in itertools.permutations(candidate['numbers']):
          ...:             yield permuted_candidate
          ...:

[ins] In [02]: {candidate for candidate in combination_generator([1, 2], 5, 5)}
Out[02]:
{(1, 1, 1, 1, 1),
 (1, 1, 1, 2),
 (1, 1, 2, 1),
 (1, 2, 1, 1),
 (1, 2, 2),
 (2, 1, 1, 1),
 (2, 1, 2),
 (2, 2, 1)}

Answer 5

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

def find_addend_combinations(sum_value, addend_choices, base=0, history=None):
    if history is None: history = []

    if base == sum_value:
        return tuple(history)
    elif base > sum_value:
        return None
    else:
        results = []
        for v in addend_choices:
            r = find_addend_combinations(sum_value, addend_choices, base + v,
                                         history + [v])
            if isinstance(r, tuple):
                results.append(r)
            elif isinstance(r, list):
                results.extend(r)
        return results

Вы могли бы написать последнюю часть для понимания списка, но я думаю, что этот путь более понятен.