Finding number of integer partitions

Question

I am trying to find number of integer partitions of given n - number. If I have n == 4, the answer should be 5 because:

1. \$4 = 1+1+1+1\$
2. \$4 = 2+1+1\$
3. \$4 = 3+1\$
4. \$4 = 2+2\$
5. \$4 = 4\$

My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

def get_answer(n):
    if n == 0:
        yield []
        return
    for p in get_answer(n-1):
        yield [1] + p
        if p and (len(p) < 2 or p[1] > p[0]):
            yield [p[0] + 1] + p[1:]
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))

Answer 1

A slightly more efficient dynamic programming approach means you only need O(n) space:

def partitions(n):
    parts = [1]+[0]*n
    for t in range(1, n+1):
        for i, x in enumerate(range(t, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
partitions(50)

Out[]:
204226

Note: this is trivial to extend to the coin change problem (the number of ways you can make change with certain coins: Ways to make change for a dollar), by restricted the values in the outer loop, e.g.:

def coin_change(n, coins):
    parts = [1]+[0]*n
    for c in coins:
        for i, x in enumerate(range(c, n+1)):
            parts[x] += parts[i]
    return parts[n]

In []:
coin_change(100, {1, 5, 10, 25, 50, 100})

Out[]:
293

Answer 2

My code works properly but the matter is that it counts big numbers for a very long time. I have no idea how to optimize my code. Maybe you can help me to make it faster?

...
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))

Don't count. Calculate.

The Wikipedia article on partitions gives the Hardy-Ramanujan estimate \$P(n) = \Theta(n^{-1} e^{k \sqrt n})\$ with \$k=\pi \sqrt\frac23\$. Since your code finds the partitions to count them, and since the "average" partition has a lot of \$1\$s, your running time is \$\Omega(e^{k \sqrt n})\$.

The Wikipedia article also gives a number of recurrence relations, including one which uses generalised pentagonal numbers (giving a running time of \$\Theta(n^{1.5})\$), and another which uses the sum of divisors function (giving a running time of \$\Theta(n^2)\$ if you pre-calculate the sum of divisors using e.g. the sieve of Eratosphenes). An alternative quadratic approach (which you could find by following the Mathworld link from Wikipedia) uses the auxiliary function \$P(n,k)\$ for the number of partitions of \$n\$ into parts of which the largest is exactly \$k\$ and the recurrence \$P(n,k)=P(n-1,k-1)+P(n-k,k)\$.

Answer 3

This is a perfect task to solve with dynamic programming. Using a C++-script found here and some additional optimization, I created this script:

num = 100
scores = [[int(j==0 and i>0) for i in range(num)] for j in range(num)]
max_part = num-1
calculated = [1]

def get_combinations(n, x = max_part):
    for i in range(calculated[0], n+1):
        for j in range(1, x+1):
            if (i-j<0):
                scores[i][j] = scores[i][j-1]
                continue
            scores[i][j] = scores[i][j-1] + scores[i-j][j];
    calculated[0] = n
    return scores[n][x]

print(get_combinations(50))

This script outputs 204226, and additionally its output is identical for any input value (I only tested up to 65, because the function in your question ran slowly after that).

The major drawback of the dynamic solution is that it is space inefficient. To calculate get_combinations(n), one must use O(n^2) memory to store the scores-array. However, it performs much better for large values of n. And an additional feature (my addition to the C++-script) is that if you run the function multiple times, it doesn't recalculate any numbers.

Thus, if get_combinations(5) has been calculated, then a subsequent call to get_combinations(2) only requires an array lookup, and a subsequent call to get_combinations(10) is faster.

This function should work without issues for any n under 1000 (for input larger than 100 the variable num needs to be adjusted), and is 400 times faster for n = 65 on my machine in the worst case. Sequentially calculating all values between 1 and 1000 runs in <0.5s.