# Integer Partition with Distinct Partsself.__wrap_b=(t,n,e)=>{e=e||document.querySelector([data-br="\${t}"]);let s=e.parentElement,r=B=>e.style.maxWidth=B+"px";e.style.maxWidth="";let o=s.clientWidth,u=s.clientHeight,a=o/2-.25,c=o+.5,p;if(o){for(r(a),a=Math.max(e.scrollWidth,a);a+1<c;)p=Math.round((a+c)/2),r(p),s.clientHeight===u?c=p:a=p;r(c*n+o*(1-n))}e.__wrap_o||(typeof ResizeObserver!="undefined"?(e.__wrap_o=new ResizeObserver(()=>{self.__wrap_b(0,+e.dataset.brr,e)})).observe(s): false&&0)};self.__wrap_b(":R4pmmmja:",1)

Number of ways to write an integer as the sum of a decreasing sequence, e.g., 5=4+1=3+2

## Question

How many ways can you write an integer n as the sum of a decreasing sequence(excluding n+0)?

Let’s look at an example from Wikipedia:

Alternatively, we could count partitions in which no number occurs more than once. Such a partition is called a partition with distinct parts. If we count the partitions of 8 with distinct parts, we also obtain 6:

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

The problem boils down to find the number of partition with distinct parts and simply subtract 1 from it. So I’ll focus on the core part.

## Solution

Doing it by hand is easy. We choose the first element, e.g., 5, figure out 8-5=3, and try to split 3 into smaller parts. For human beings, checking “3 is less than 5” on paper happens in an instant. But we need a way to tell the computer what is the current max, so it knows possible choices for the next number.

### Recursion

#### Visualize the result

Before we directly count the total number of sequences, it helps to visualize the result. Based on the idea from StackOverflow:

Translate partition(n, maxi) into English: Parition the number n into a decreasing sequence where the first element(largest one) is no bigger than maxi.

min(n-i, i-1) is to ensure the sequence is decreasing, and the max is no more than the number itself. To see that, let $M = min(n-i, i-1) \Rightarrow M \leq i-1 \text{ and } M \leq n-i$.

This also avoids extra calculations because the size for each part can’t be more than what we have. For example, partition(5, 5) = partition(5, 14), so we don’t need to run the loop from 6 to 14.

def partition(n: int, maxi: int)-> List[int]:
if n == 0: return [[]]
results = []
# 1 <= i <= n. If max = 0, we won't have any partition.
for i in range(maxi, 0, -1):
# n-i is what remains after taking away i from n.
subresults = partition(n - i, min(n-i, i-1))
results.extend([ [i] + sub for sub in subresults])
return results
def partition(n: int, maxi: int)-> List[int]:
if n == 0: return [[]]
results = []
# 1 <= i <= n. If max = 0, we won't have any partition.
for i in range(maxi, 0, -1):
# n-i is what remains after taking away i from n.
subresults = partition(n - i, min(n-i, i-1))
results.extend([ [i] + sub for sub in subresults])
return results

> partition(5, 5)
[, [4, 1], [3, 2]]

> partition(10, 5)
[[5, 4, 1], [5, 3, 2], [4, 3, 2, 1]]

> partition(10, 10)
[, [9, 1], [8, 2], [7, 3], [7, 2, 1], [6, 4], [6, 3, 1], [5, 4, 1], [5, 3, 2], [4, 3, 2,1]]
> partition(5, 5)
[, [4, 1], [3, 2]]

> partition(10, 5)
[[5, 4, 1], [5, 3, 2], [4, 3, 2, 1]]

> partition(10, 10)
[, [9, 1], [8, 2], [7, 3], [7, 2, 1], [6, 4], [6, 3, 1], [5, 4, 1], [5, 3, 2], [4, 3, 2,1]]

#### Let’s count the total number

Base case is 0. When we have count_p(0, i-1), it means n=i or n=0, so the only possible partition is n = n no matter what the max is.

def count_p(n, maxi):
if n == 0: return 1
result = 0
for i in range(maxi, 0, -1):
result += count_p(n-i, min(n-i, i-1))
return result
def count_p(n, maxi):
if n == 0: return 1
result = 0
for i in range(maxi, 0, -1):
result += count_p(n-i, min(n-i, i-1))
return result

> count_p(10, 10)
10
> count_p(5, 5)
3
> count_p(200, 200)
... waiting ...
> count_p(10, 10)
10
> count_p(5, 5)
3
> count_p(200, 200)
... waiting ...

It works, but it’s super inefficient. To see where recalculations happen, I modified the function as below:

from collections import Counter

def count_p_recalc(n, maxi, pool):
if n == 0: return pool
for i in range(maxi, 0, -1):
pool[(n, i)] += 1
pool = count_p_recalc(n - i, min(n - i, i - 1), pool)
return pool

print(count_p_recalc(20, 20, Counter()).most_common(5))

# Result format: ((n, maxi), #number of recalcualtions)
# [((1, 1), 29), ((2, 1), 25), ((3, 1), 21), ((4, 1), 17), ((2, 2), 15)]
from collections import Counter

def count_p_recalc(n, maxi, pool):
if n == 0: return pool
for i in range(maxi, 0, -1):
pool[(n, i)] += 1
pool = count_p_recalc(n - i, min(n - i, i - 1), pool)
return pool

print(count_p_recalc(20, 20, Counter()).most_common(5))

# Result format: ((n, maxi), #number of recalcualtions)
# [((1, 1), 29), ((2, 1), 25), ((3, 1), 21), ((4, 1), 17), ((2, 2), 15)]

If these results are stored somewhere, we can avoid all recalculations and just use it.

### Dynamic Programming

def P(n):

size = n + 1
# initialize the table
p = [[0 for _ in range(size)] for _ in range(size)]

p = 1
for i in range(size):
for j in range(1, size):
# The same idea: we don't care about more than what we have
if j <= i:
p[i][j] = p[i][j - 1] + p[i - j][min(i - j, j - 1)]

return p[n][n]
def P(n):

size = n + 1
# initialize the table
p = [[0 for _ in range(size)] for _ in range(size)]

p = 1
for i in range(size):
for j in range(1, size):
# The same idea: we don't care about more than what we have
if j <= i:
p[i][j] = p[i][j - 1] + p[i - j][min(i - j, j - 1)]

return p[n][n]

Let’s decipher the highlighted line:

p[i][j]: Partition the integer i into a decreasing sequence with the first element(largest one) **less than or equal to ** j. Here we are accumulating the result. Say we want to partition 8. After selecting 5 as the first element, we want to find all decreasing sequences starting with 4 or less that sum to 8-5=3. As long as the first element is less than 5, the sequence is valid.

p[i][j-1] +: Accumulate the result as explained above.

p[i-j][min(i-j, j-1)]: Find all valid subsequences from i-j(what’s left). This corresponds to our recursion partitoin(n-i, min(n-i, i-1)).

Finally, we can find our result at p[n][n]: partition the integer n with the starting element less than or equal to n. This is exactly what we’re looking for.

If you want to exclude n=n+0, just return p[n][n]-1.

Here’s the table from P(8). The result is at p[8, 8] = 6 as we expected.

[
[1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 2, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 2, 0, 0, 0, 0],
[0, 0, 0, 1, 2, 3, 0, 0, 0],
[0, 0, 0, 1, 2, 3, 4, 0, 0],
[0, 0, 0, 0, 2, 3, 4, 5, 0],
[0, 0, 0, 0, 1, 3, 4, 5, 6]
]
[
[1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 2, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 2, 0, 0, 0, 0],
[0, 0, 0, 1, 2, 3, 0, 0, 0],
[0, 0, 0, 1, 2, 3, 4, 0, 0],
[0, 0, 0, 0, 2, 3, 4, 5, 0],
[0, 0, 0, 0, 1, 3, 4, 5, 6]
]

Find me on Twitter or write me an email