I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions. For example:
The partitions of size 2 for number 5 are:
- [4, 1]
- [3, 2]
The partitions of size 3 for number 6 exists only of:
- [3, 2, 1]
Notice that [2, 2, 2] isn't a partition because it has a repeating use of 2.
I currently have implemented a dynamic algorithm that finds the amount of partitions that allow repetition. Here $m$ is is the number and $n$ is the size of the partitions.
def count_partitions(m, n): def e_at(i,j): if i == j and j == -1: return 1 if i < j: return 0 else: return p[i][j] p = [[-1 for _ in range(n)] for _ in range(m)] for i in range(m): p[i] = 1 for i in range(m): for j in range(1, min(i + 1, n)): if i < 2*j: p[i][j] = e_at(i-1,j-1) else: p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j) return p[m-1][n-1]
I've also got a program to generate all the different distinct k-partitions of a number $n$
def generate_partitions(n, k): if n == 0: return  def rec_partition(m, b, n, a, l): if m == 0: l.append(conj_partition(a[:n])) else: c = a[n] for i in range(1, min(b,m) + 1): a[n] = i rec_partition(m-i, i, n+1, a, l) a[n] = c def has_double(l): for i in range(len(l) - 1): if l[i] == l[i+1]: return True return False l =  a =  * n a = k rec_partition(n - k, k,1, a, l) return sorted([p for p in l if not has_double(p)], reverse=True)
So far the only way I found to get the number of distinct k-partitions is to generate them all and take the length of the returned list.
However I feel like there would be a better way to get the amount without generating them all by modifying the dynamic programming algorithm above. But I haven't had any luck with that.
Anyone has any idea that would help?