Python Program to write an integer as a sum of r positive integers-CodePudding

I want to create a python program which returns all possible ways of writing an integer (say n) as a sum of r positive integers.

My code is as follows :

def f(n,r):
cache = {}

l1 = []
for i in range(1,n):
    l1.append([i,n-i])
    
    
if r ==2 :
    cache[tuple([n,r])] = l1
    return l1

elif (n,r) in cache:
    return cache[(n,r)]
    
else:
    lr = []
    for i in range (1,n):
        for x in f(n-i,r-1):
            x.append(i)
            lr.append(x)
    cache[tuple([n,r])] = lr        
    return lr

It works well till n = 20 for any value of r but after that it's really slow, which is kinda expected because recurrence is slow. How can I achieve this without using recurrence ?

CodePudding user response：

Generation in lexicographic order.

Note that any generation method won't be fast for large n,r values due to exponential grow of number of partitions.

from itertools import combinations
def parts(n,r):
    result = []
    for comb in combinations(range(n-1), r-1):
        parts = [comb[0] 1] [comb[i]-comb[i-1] for i in range(1,r-1)] [n-1-comb[-1]]
        #print(comb, parts)
        result.append(parts)
    return(result)

print(parts(6,3))

>>>[[1, 1, 4], [1, 2, 3], [1, 3, 2], [1, 4, 1], [2, 1, 3], [2, 2, 2], 
    [2, 3, 1], [3, 1, 2], [3, 2, 1], [4, 1, 1]]

CodePudding user response：

A simple recursion with lru_cache:

>>> from functools import lru_cache
>>> @lru_cache(None)
... def f(n, r):
...     if r == 1:
...         return (n,),
...     return tuple((i,)   comb for i in range(1, n) for comb in f(n - i, r - 1))
...
>>> f(20, 3)
((1, 1, 18),
 (1, 2, 17),
 (1, 3, 16),
 ...
 (17, 1, 2),
 (17, 2, 1),
 (18, 1, 1))

Note: if we fix r to 10 and continue to increase n, the running time of the function will still gradually become unacceptable, because every time n increases by 1, the length of the obtained result will greatly increase, and the time spent on the concatenated of tuples (or lists) will also be more and more:

>>> {i: len(f(i, 10)) for i in range(10, 30)}
{10: 1,
 11: 10,
 12: 55,
 13: 220,
 14: 715,
 15: 2002,
 16: 5005,
 17: 11440,
 18: 24310,
 19: 48620,
 20: 92378,
 21: 167960,
 22: 293930,
 23: 497420,
 24: 817190,
 25: 1307504,
 26: 2042975,
 27: 3124550,
 28: 4686825,
 29: 6906900}