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 =$$$$\{<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)?

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})$.
• Thanks for the answer. Do you see a way of computing the entire vector in linear time (i.e. $O(n+k)$)? – R B Oct 2 '14 at 10:17
• @RB I don't see linear time immediately. If you can bring the sum for $s_m$ into closed form, you could search $m$ by binary search in each step for $O(n\log n)$ overall time. – FrankW Oct 2 '14 at 10:21
• Hmm, I've tried programming this but it doesn't quite seem to work. If we take the example I had in the question ($n=4,k=3$) and $i=15$, we should get (4,0,0). The first coordinate indeed is 4, but then $s_3=9$ and $P_{0,2}(i-m)=P_{0,2}(6)$ is not defined. – R B Oct 2 '14 at 10:34
• $s_3$ should be 15. Did you run the sum from $j=1$ instead of $j=0$? – FrankW Oct 2 '14 at 10:59
• Yes, works perfectly now, thank you very much ! – R B Oct 2 '14 at 11:07