Комбинаторика взвешенных строк: подсчитайте количество целочисленных комбинаций с суммой (целые числа) = m

Question

Учитывая список целых чисел, например,

l = [3, 5, 8, 13]

и целое число, например,

m = 13

подсчитать количество комбинаций целых чисел, которые имеют сумму = m, например,

combinations = len([[8, 5], [5, 8], [13], [3, 5, 5], [5, 5, 3], [3, 5, 3], ...])

Для малых значений m я могу использовать эту рекурсию (линейное рекуррентное отношение, подобное Фибоначчи):

def RecursiveCount(m, integers):
    count = 0
    if m < 0:
        return 0
    if m == 0:
        return 1
    for i in integers:
        count += RecursiveCount(m-i, integers)
    return count

Но для больших l и m он замедляется и предлагается использовать динамическийпрограммирование для запоминания уже решенных комбинаций для уменьшения рекурсивных вызовов.К сожалению, я не могу это реализовать.Я пытался прочитать это, но это не помогло https://bio.informatik.uni -jena.de / wp / wp-content / uploads / 2014/09 / book_handout_3.pdf

Редактировать: обучениерезультат был бы наибольший, если бы я смог реализовать его с помощью динамического программирования

Answer 1

Это решение не использует динамическое программирование, но значительно быстрее:

import math
from functools import reduce

def num_seq_sum(m, nums):
    if m == 0:
        return 1
    # Avoid repeated numbers
    nums = list(set(nums))
    # Begin with no numbers picked
    base = [0] * len(nums)
    return sum(_seqs_sum_rec(m, nums, base, 0))

def _seqs_sum_rec(m, nums, current, i):
    if i >= len(nums):
        raise StopIteration
    # Try without adding current number, add next numbers
    yield from _seqs_sum_rec(m, nums, current, i + 1)
    # Try adding current number
    n = nums[i]
    # While we can fit more copies of current number
    while m > n:
        current[i] += 1
        m -= n
        yield from _seqs_sum_rec(m, nums, current, i + 1)
    # If we can fit exactly one more
    if m == n:
        current[i] += 1
        # Number of permutations of the current combination
        yield _num_permutations(current)
    # Undo additions for parent call
    current[i] = 0

def _num_permutations(comb):
    return math.factorial(sum(comb)) // reduce(lambda a, b: a * b, (math.factorial(c) for c in comb), 1)

nums = [3, 5, 8, 13]
m = 13

print(RecursiveCount(m, nums) == num_seq_sum(m, nums))
# True

Небольшой тест производительности:

nums = [1, 3, 5, 8, 10, 15]
m = 30

%timeit RecursiveCount(m, nums)
# 1.48 s ± 6.86 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit num_seq_sum(m, nums)
# 4.77 ms ± 85.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 2

Простое время поиска для этого составляет O(n * k), где n - сумма, а k - число целых чисел в списке.Область поиска может быть ограничена O(max(list)), но для удобства мы можем просто использовать O(n).

Код Python:

def f(n, nums):
  m = [0 for i in range(n + 1)]

  for s in range(min(nums), n + 1):
    for c in nums:
      if c == s:
        m[s] += 1
      if c < s:
        m[s] += m[s - c]

  return m[n]

Выход :

nums = (3, 5, 8, 13, 15, 20)
m = 200

t0 = time.time()
x = num_seq_sum(m, nums) # jdehesa's code
t1 = time.time()

print(x, t1-t0) # 233354368688517335733 4.085544586181641

t0 = time.time()
x = f(m, nums)
t1 = time.time()
print(x, t1-t0) # 233354368688517335733 0.0004315376281738281

t0 = time.time()
x = RecursiveCount(m, nums) # using @functools.lru_cache()
t1 = time.time()
print(x, t1-t0) # 233354368688517335733 0.0006241798400878906

Answer 3

Вы можете легко добавить памятку, добавив декоратор @functools.lru_cache к своей рекурсивной функции.

@functools.lru_cache()
def RecursiveCount(m, integers):
    ...

Это автоматически кеширует результаты для определенных параметров и проверяет их сначалаповторный вызов функции, что значительно сокращает количество вызовов и, следовательно, время выполнения.Однако для этого требуется, чтобы все параметры были хэшируемыми, т. Е. Вам нужно было бы передать integers как tuple.

Пример для RecursiveCount(20, tuple(range(1, 10)))): Результат: 518,145;вызов функции без напоминания: 4 672 513;с памяткой: 29.

(Если это упражнение по DP, это, вероятно, не вариант, но в остальном это хорошо работает на практике.)