Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering

Question

Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins.

Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\{0,1,\ldots,n\}^k$ such that the sum of the entries is exactly $n$.

For example, if $n=4$ and $k=3$, we get: $$\mathcal P =$$$$ \{<0,0,4>,<0,1,3>,<0,2,2>,<0,3,1>,<0,4,0>,<1,0,3>,<1,1,2>,<1,2,1>,<1,3,0>,<2,0,2>,<2,1,1>,<2,2,0>,<3,0,1>,<3,1,0>,<4,0,0>\}$$

Simple combinatorics (Stars and bars) tells us that $|\mathcal {P}| =$$n+k-1 \choose n$.

Now the goal would be to compute $p\in \mathcal P$ given it's index in a lexicographical ordering on $\mathcal P$ (alternatively, consider each vector as a number in base $n+1$ and order $\mathcal P$ based on the number).

In the example above $\mathcal P$ is ordered, so for example, given the input $3$, we'd like to output $<0,2,2>$.

So the question is:

How to we compute $\mathcal P(i)$ efficiently (without enumerating all $\leq i$ partitions)?

Answer 1

The procedure of generating the $i$-th structure according to some ordering of a combinatorial class is called unranking.

In your specific case an unranking algorithm for $P_{n,k}(i)$ can be created as follows:

Define $s_m := \sum_{j=0}^m |P_{n-j,k-1}|$, the number of vectors that start with $m$ or a smaller number, $s_{-1}=0$.

• If $k=1$, the vector contains the single entry $n$.
• Otherwise,
  • The first entry in the vector is $m$ so that $s_{m-1} < i \le s_m$.
  • The remaining vector is $P_{n-m,k-1}(i-s_{m-1})$.