Rank of Partition with specific length

Question

How can I determine the rank/index of a partition of integer n with length k?

For instance, if n=10 and k=3, the possible partitions (sorted in reverse lexicographic order) are:

0 (8, 1, 1)
1 (7, 2, 1)
2 (6, 3, 1)
3 (6, 2, 2)
4 (5, 4, 1)
5 (5, 3, 2)
6 (4, 4, 2)
7 (4, 3, 3)

and I want to know the index of a specific partition, such as [5, 3, 2].

What is an efficient method to obtain this index without generating all the partitions?

I've tried using lehmer codes to no avail, I've also tried writing a helper function num_partitions(n, k, p) which returns the number of partitions of n with k parts and the largest part not exceeding p

def num_partitions(n, k, p):
  if n < 0 or k < 0 or p <= 0:
    return 0
  if n == 0 and k == 0:
    return 1
  return (partition_count_p(n - p, k - 1, p)
          + partition_count_p(n, k, p - 1))

But i just can't seem to fully wrap my head around it, perhaps a literature i am not aware of 🤔

Answer 1

The index of a partition is the number of reverse-lexically smaller partitions. You can divide this number into two parts: all partitions with a smaller last number, and smaller partitions with the same last number.

def partition_index(list):
   k = len(list)
   n = sum(list)

   # every number is guaranteed > this
   # we are partitioning the excess
   toosmall = 0

   index = 0

   while (k>1):
       last = list[k-1] - toosmall

       # count partitions of n into k parts with smaller last
       if last > 1:
           # you already wrote this function
           index += num_partitions(n,k,last-1)

       # loop to count smaller partitions with the same last number
       k -= 1
       n -= last

       # since we only accept partitions in decreasing order...
       toosmall += (last-1)
       n -= k*(last-1)

    return index

Answer 2

I eventually figured this out, figured i should post as a separate answer so it may help someone else that comes across this.

So it's inspired by this: Find the lexicographic order of an integer partition, but instead of using p(n, k) which returns count of partitions with at most k parts, we use the variation that only returns the count of partitions with length k:

def p(n, k):
  '''Return total number of partition for integer n having length k'''
  if n == 0 and k == 0:
    return 1
  if k == 1 or n == k:
    return 1
  if k > n:
    return 0
  return p(n-1, k-1) + p(n-k, k)

def num_partitions(n, k, p):
  '''Returns the number of partitions of n with k parts and the largest part not exceeding p'''
  if n < 0 or k < 0 or p <= 0:
    return 0
  if n == 0 and k == 0:
    return 1
  return (num_partitions(n - p, k - 1, p)
          + num_partitions(n, k, p - 1))

Then to compute the rank, we simply do (inspired by [1]):

def partition_rank(arr):
  n = _n = sum(arr)
  k = _k = len(arr)
  r = 0
  for v in arr:
    r += num_partitions(n, k, v-1)
    n -= v
    k -= 1
  return p(_n, _k) - r - 1

Test:

arr = [(8, 1, 1), (7, 2, 1), (6, 3, 1), (6, 2, 2), (5, 4, 1), (5, 3, 2), (4, 4, 2), (4, 3, 3)]
for partition in arr:
  print(partition, partition_rank(partition))

Output:

(8, 1, 1) 0
(7, 2, 1) 1
(6, 3, 1) 2
(6, 2, 2) 3
(5, 4, 1) 4
(5, 3, 2) 5
(4, 4, 2) 6
(4, 3, 3) 7

You could easily employ dynamic programming to make the computation more efficient.