For positive integers n and k, let a "k-partition of n" be a sorted list of k distinct positive integers that add up to n, and let the "rank" of a given k-partition of n be its position in the sorted list of all of these lists in lexicographic order, starting at 0.
For example, there are two 2-partitions of 5 (n = 5, k = 2): [1,4] and [2,3]. Since [1,4] comes before [2,3] in lexicographic order, the rank of [1,4] is 0 and the rank of [2,3] is 1.
So, I want to be able to do two things:
Can I do this without having to compute all the k-partitions of n that come before the one of interest?
This question is different from other because we are here talking about integer partitions and not just combinations.
Here is a solution in Python that relies on two ideas. First, dynamic programming to count partitions without generating them. Second, if the first value is i then we can look at this as an i * k box with a partition of n-i*k into k-1 pieces resting on top.
partition_cache = {}
def distinct_partition_count (n, k):
if n < k:
return 0
elif n < 1:
return 0
elif k < 1:
return 0
elif k == 1:
return 1
elif (n, k) not in partition_cache:
answer = 0
for i in range(1, n//k + 1):
answer = answer + distinct_partition_count(n - i*k, k-1)
partition_cache[(n, k)] = answer
return partition_cache[(n, k)]
def rank_distinct_partition (values):
values2 = sorted(values)
n = sum(values)
k = len(values)
answer = 0
highwater = 0
for v in values:
rise = v - highwater
for i in range(1, rise):
answer = answer + distinct_partition_count(n - k*i, k-1)
highwater = v
## BUG HERE: was n = n - rise
n = n - rise * k
k = k - 1
return answer
def find_ranked_distinct_partition (n, k, rank):
if k == 1 and rank == 0:
return [n]
elif distinct_partition_count(n, k) <= rank:
return None
elif rank < 0:
return None
else:
i = 1
while distinct_partition_count(n - i*k, k-1) <= rank:
rank = rank - distinct_partition_count(n - i*k, k-1);
i = i + 1
answer = find_ranked_distinct_partition(n - i*k, k-1, rank)
return [i] + [j + i for j in answer]
print(rank_distinct_partition([2, 3]))
print(find_ranked_distinct_partition(5, 2, 1))