CODEWITHSUNDEEP
pythonfunction
Bolce Bussiere
Bolce Bussiere

Reputation: 167

Partitions of an integer into elements of a set

I want to define a function, which, when given a set (of positive integers) and an integer, returns the number of partitions of that integer into elements of the set. For example,

partitions({1,2,3},5)=5

Since 1+1+1+1+1=5, 1+1+1+2=5, 1+2+2=5, 1+1+3=5, and 2+3=5.

What would be the most efficient way of implementing this in Python?

Note: It doesn't need to return the actual partitions, just the number of them.

Upvotes: 1

Views: 159

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476813

In case the values are integral and positive (so in the set {1, 2, 3, ...}) We can use a dynamic programming approach here:

import numpy as np

def count_subsetsum(xs : set, s : int):
    v = np.zeros(s+1, dtype=int)
    v[0] = 1
    for x in xs:
        b = np.zeros(s+1, dtype=int)
        b[:] = v[:]
        for d in range(x,s+1,x):
            b[d:] += v[:s-d+1]
        v = b
    return v[s]

Here we thus consider a vector v. Initially the vector contains only zeros, except for v[0] that is equal to 1 (since we can construct exactly one sum with a total of zero: considering no elements at all).

Now we will update the vector. We will fetch a value x from the iterable xs, and we will "sum up the vector". We do this by iteratively adding v[:s-d+1] to the end of the vector b. v[:s-d+1] contains all elements up to (and excluding) s-d-1. We add this to b[d:]. So the value of v[i] is added to b[i+d] for all the elements in the vector. We do this for d in every multiple of x. So the first upgrade we virtually "add one x" to every element in v. The second time, we "add a two xs" to every sum we already constructed.

We do this for every x in xs, and at the end v[s] thus contains all ways we can construct a sum that sums up to s. So we return that v[s].

For example:

>>> count_subsetsum({1,2,3},5)
5  # 1+1+1+1+1 1+1+1+2 1+1+3 1+2+2 2+3
>>> count_subsetsum({1,2},5)
3  # 1+1+1+1+1 1+1+1+2 1+2+2
>>> count_subsetsum({1,3},5)
2  # 1+1+1+1+1 1+1+3
>>> count_subsetsum({1,3,5},5)
3  # 1+1+1+1+1 1+1+3 5
>>> count_subsetsum({1,2,4},5)
4  # 1+1+1+1+1 1+1+1+2 1+2+2 1+4
>>> count_subsetsum({1},5)
1  # 1+1+1+1+1

(I added a comment with the sums for every example)

The advantage of using a dynamic programming approach over a brute force approach is that it does not scale exponentially. Take for instance the following query:

>>> count_subsetsum({1,2,5,7,22},15921)
1746490921624

That is 1'746'490'921'624. Even if we manage to generate a billion results per second, it would still take 1'746 seconds (which is roughly half an hour). So usually counting is faster than enumerating.

Upvotes: 1

Related Questions