Rank and unrank integer partition with k parts

Question

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:

Given n, k, and a k-partition of n, I want to find the rank of that k-partition of n.
Given n, k, and a rank, I want to find the k-partition of n with that rank.

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.

I think it it can be done via recursion and a 2 dimensional array. But i didnt figured out, how it can be done. :-( — TTho Einthausend, Jun 26 '19 at 21:31
Possible duplicate of [Rank and unrank Combination with constraints](https://stackoverflow.com/questions/56693282/rank-and-unrank-combination-with-constraints) — Yonlif, Jun 26 '19 at 22:16
@Yonlif I think it is not duplicate but very similar idea solution. — aropan, Jun 26 '19 at 22:40

btilly · Accepted Answer · 2023-03-20T00:16:53.797

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))

Doesnt work for ```n=101, k=10, rank=129905``` constructed with ```2,3,5,7,9,10,13,15,18,19``` — TTho Einthausend, Aug 28 '19 at 19:04
@TThoEinthausend I have verified the bug. I'm trying to track down where the mistake is. But for `n=101, k=10` it first happens with `rank=24`. — btilly, Aug 28 '19 at 22:47
@TThoEinthausend Sorry it took me so long. The bug is fixed. I marked where in the code the bug was. — btilly, Sep 03 '19 at 23:50
@BiereaguSochima The problem asked to find partitions into DISTINCT integers. Partitions with duplicates are not partitions of the desired type, and therefore should not be found or counted. — btilly, Mar 20 '23 at 00:19

Rank and unrank integer partition with k parts

1 Answers1

Linked