2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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})$.
$\endgroup$
  • $\begingroup$ Thanks for the answer. Do you see a way of computing the entire vector in linear time (i.e. $O(n+k)$)? $\endgroup$ – R B Oct 2 '14 at 10:17
  • 1
    $\begingroup$ @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. $\endgroup$ – FrankW Oct 2 '14 at 10:21
  • $\begingroup$ 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. $\endgroup$ – R B Oct 2 '14 at 10:34
  • 1
    $\begingroup$ $s_3$ should be 15. Did you run the sum from $j=1$ instead of $j=0$? $\endgroup$ – FrankW Oct 2 '14 at 10:59
  • $\begingroup$ Yes, works perfectly now, thank you very much ! $\endgroup$ – R B Oct 2 '14 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.