CODEWITHSUNDEEP
pythondynamic-programming
Benni
Benni

Reputation: 785

Combinatorics of Weighted Strings: Count the number of integer combinations with sum(integers) = m

Given a list of integers e.g.

l = [3, 5, 8, 13]

and an integer e.g.

m = 13

count the number of integer combinations that have sum=m e.g.

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

For small values of m, I can use this recursion (Fibonacci-like linear recurrence relation):

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

But for larger l and m, it gets to slow and it´s proposed to use dynamic programming to memorize already solved combinations to reduce the recursive calls. Unfortunately, I'm not able to implement this. I tried reading this, but it didn´t help https://bio.informatik.uni-jena.de/wp/wp-content/uploads/2014/09/book_handout_3.pdf

Edit: The learning outcome would be the greatest, if I would be able to implement it using dynamic programming

Upvotes: 1

Views: 143

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23945

A straightforward search time for this is O(n * k), where n is the sum and k is the number of integers in the list. The search space can be confined to O(max(list)) but for convenience we can just use O(n).

Python code:

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]

Output:

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

Upvotes: 2

javidcf
javidcf

Reputation: 59731

This solution doesn't use dynamic programming but is significantly faster:

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

A small performance test:

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)

Upvotes: 1

tobias_k
tobias_k

Reputation: 82929

You can easily add memoization by adding the @functools.lru_cache decorator to your recursive function.

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

This will automatically cache the results for certain parameters and check that cache first before calling the function again, dramatically reducing the number of calls, and hence runtime. However, this requires all the parameters to be hashable, i.e. you'd have to pass integers as a tuple.

Example for RecursiveCount(20, tuple(range(1, 10)))): Result: 518,145; function call without memoization: 4,672,513; with memoization: 29.

(If this is for an exercise in DP, this is probably not an option, but otherwise this works well in practice.)

Upvotes: 3

Related Questions