Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering 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 =$$$$ \{&lt;0,0,4&gt;,&lt;0,1,3&gt;,&lt;0,2,2&gt;,&lt;0,3,1&gt;,&lt;0,4,0&gt;,&lt;1,0,3&gt;,&lt;1,1,2&gt;,&lt;1,2,1&gt;,&lt;1,3,0&gt;,&lt;2,0,2&gt;,&lt;2,1,1&gt;,&lt;2,2,0&gt;,&lt;3,0,1&gt;,&lt;3,1,0&gt;,&lt;4,0,0&gt;\}$$

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
$&lt;0,2,2&gt;$.

So the question is:


  How to we compute $\mathcal P(i)$ efficiently (without enumerating all $\leq i$ partitions)?
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} &lt; i \le s_m$.
The remaining vector is $P_{n-m,k-1}(i-s_{m-1})$.