1

Following this thread python-integer-partitioning-with-given-k-partitions

I want to find the number of such partitions (where the minimum part is equal to 1), but the following solution (in the thread and many other threads) gives the exact partitions of such an integer into k parts.

Since the algorithm is recursive and gives each partition I thought it might help me to just count the number of such partitions with memoization or dynamic programming, but I couldn't come up with a good solution.

So for example for n=7 and k=2 the result will be res=3 intead of res=[[1,6],[2,5],[3,4]]

linuxbeginner
  • 39
  • 1
  • 7
  • Would the solution where order matters help? E.g., for n=7, k=2 it would give 6 b/c it would include res=[[1,6],[2,5],[3,4],[4,3],[5,2],[6,1]]. If useful, this could be found quickly. – Dave Jul 20 '23 at 00:18
  • It does answer the question but it uses a recursive solution (though can be converted to for loop), but I think the formula from Mathematica helped me solve this problem better. Dave: the sequence must be in increasing order (If the order doesn't matter it just a combinatorics question) – linuxbeginner Jul 20 '23 at 16:17

1 Answers1

1

After consulting the thread in Mathematica Integer partition of n into k parts recurrence, came up with the following solution:

def p(n: int, k: int) -> int:
   memo: list[list[int]] = [[0 for _ in range(k+1)] for _ in range(n + 1)]
   for i in range(1,n + 1):
       memo[i][1] = 1

   for i in range(2,n + 1):
       for j in range(2, k+1):
           memo[i][j] += memo[i-1][j - 1]
           if i - j >= j :
               memo[i][j] += memo[i - j][j]

   return memo[n][k]
linuxbeginner
  • 39
  • 1
  • 7