# Finding number of integer partitions

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
yield  + p
if p and (len(p) < 2 or p > p):
yield [p + 1] + p[1:]
number_of_partitions=lambda n:sum(1 for _ in get_answer(n))

• This will be of combinatorial complexity any way you do it - so I think we need a dynamic programming / memoization approach here. Jul 30, 2017 at 10:56
• Use a concise generating function approach Jul 30, 2017 at 12:47
• @hjpotter92 I tried them all. Only accel_asc is a bit faster but it requires much more memory. That's why it will not do for me. Jul 30, 2017 at 14:41
• @Nikita.K Are there any restrictions to what you can use? It seems like accel_asc is your best option in terms of speed. Otherwise, you're stuck with your funciton. In this case, I would first try a different implementation such as PyPy or maybe augment Python a bit with Cython. After that I would just use another language honestly.
– Dair
Jul 30, 2017 at 23:11
• @Dair Actually this task is from Codewars. So, I can't use any implementations. Also, Python is the only language I know. Jul 31, 2017 at 4:40

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

def partitions(n):
parts = +*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 = +*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


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)$.

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 = 

def get_combinations(n, x = max_part):
for i in range(calculated, 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 = 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.

• You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. Jul 19, 2022 at 17:12
• FWIW this seems like justification that it is an improvement over the original: "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." Jul 19, 2022 at 18:41
• @TobySpeight The IO rule started simply by 200_success as: "Would this answer constitute a reasonable checkin log message?" with a number of real world examples. Please note the latest version of the rule is: "the minimum expectation of an insightful observation ... should be to say what parameter(s) it improves". To my eyes the section SᴀᴍOnᴇᴌᴀ quoted clearly describes an improved parameter and would be a more than valid checkin message. Hence constitutes an IO. Jul 19, 2022 at 21:49
• It's probably better to start with the observation at the beginning of the answer, and the code that illustrates the improvement afterwards. The actual review can easily be obscured by hiding it in the middle like this! Jul 20, 2022 at 18:17