Find how many combinations of integers possible to reach the result

user_13829889 0
Viewed 83

I'm a bit stuck on a python problem.

I'm suppose to write a function that takes a positive integer n and returns the number of different operations that can sum to n (2<n<201) with decreasing and unique elements. To give an example: If n = 3 then f(n) = 1 (Because the only possible solution is 2+1). If n = 5 then f(n) = 2 (because the possible solutions are 4+1 & 3+2). If n = 10 then f(n) = 9 (Because the possible solutions are (9+1) & (8+2) & (7+3) & (7+2+1) & (6+4) & (6+3+1) & (5+4+1) & (5+3+2) & (4+3+2+1)).

For the code I started like that:

def solution(n):
nb = list(range(1,n))
l = 2
summ = 0
itt = 0
for index in range(len(nb)):
    x = nb[-(index+1)]
    if x > 3:
        for index2 in range(x-1):
            y = nb[index2]
            #print(str(x) + ' + ' + str(y))
            if (x + y) == n:
                itt = itt + 1
            for index3 in range(y-1):
                z = nb[index3]
                if (x + y + z) == n:
                    itt = itt + 1
                for index4 in range(z-1):
                    w = nb[index4]
                    if (x + y + z + w) == n:
                        itt = itt + 1
                   
return itt

It works when n is small but when you start to be around n=100, it's super slow and I will need to add more for loop which will worsen the situation...

Do you have an idea on how I could solve this issue? Is there an obvious solution I missed?

math python
1 Answers

This problem is called integer partition into distinct parts. OEIS sequence (values are off by 1 because you don't need n=>n case )

I already have code for partition into k distinct parts, so modified it a bit to calculate number of partitions into any number of parts:

import functools

@functools.lru_cache(20000)
def diffparts(n, k, last):
    result = 0
    if n == 0 and k == 0:
            result = 1
    if n == 0 or k == 0:
        return result

    for i in range(last + 1, n // k + 1):
        result += diffparts(n - i, k - 1, i)
    return result

def dparts(n):
    res = 0
    k = 2
    while k * (k + 1) <= 2 * n:
        res += diffparts(n, k, 0)
        k += 1
    return res

print(dparts(201))
user_8444160
Related