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][0] = 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 = [0] * n
a[0] = 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?