An efficient algorithm for generating set partitions

This can be done recursively. Let $f(n,maxcount,maxval)$ return the list of partitions of $n$ containing no more than $maxcount$ parts and in which each part is no more than $maxval$.

• If $n=0$ return a single list containing the empty partition.
• If $n>maxcount\times maxval$ return the empty list.
• If $n=maxcount\times maxval$ return a single list consisting of the obvious solution.

Otherwise we make a series of recursive calls to $f(n-x,maxcount-1,x)$.

So to count all partitions of an integer $n$ with $m$ parts, a recursive algorithm is the obvious choice.

But when partitioning with a recursive algorithm, many calculations are repeated numerous times and with increasing values for $n$ and $m$, the number of recursions quickly becomes huge. However, the number of unique calculations can never be greater than $n\times m$. So by caching the result of each calculation in an $n\times m$ sized array, no more than $n\times m$. So calculations never need to be done after having calculated a case once, the algorithm can use the stored value.

So we can use dynamic programming. Let $f[n][m][k]$ be the number of partitions of $m$ non-decreasing positive numbers such that the sum is $n$ and the last one is $k$. Then we could easily see that the update step would be:

$f[n][m][k]→f[n+l][m+1][l]$ for every $l≥k$

To get $f[n][m]$, meaning the number of all partitions independent of which is the last number, at the end just sum over all $k$. The complexity would be $O(n^2\times m)$.