bijection $\{0, 1, \ldots, \binom{|m|}{n}-1\} \longleftrightarrow \binom{m}{n}$ I am attempting to generate random numbers which correspond to states in a game. Say there are $|m|$ squares, and $n$ pieces which can occupy the squares. Then I can have a total of $\binom{|m|}{n}$ states, given the pieces are indistinct.
However, I would like to transform the randomly generated number $\left[0, \binom{|m|}{n}\right)$ into a specific state, and for this I need a bijection $\{0, 1, \ldots, \binom{|m|}{n}-1\}$ $\longleftrightarrow$ $\binom{m}{n}$.
An algorithm that I can think of (that may work) would in essence order the pieces, and place the $i^\text{th}$ piece on the $i^\text{th}$ square to start. Then iterate over the pieces, shifting the rightmost piece right if the square is not occupied. Whenever a piece $p_0$ to the left of any other given pieces $p_1, \ldots, p_k$ is shifted right, then shift $p_1, \ldots p_k$ left as far as possible such that $p_i$ is still on a lesser square than $p_j$.
I would appreciate guidance in any other directions or any simplifications etc!
Thanks!
 A: So from what I understand, you're trying to enumerate the set of size-$n$ subsets of some fixed set $\Omega$ of size $m$ so that you can readily compute the choice of size-$n$ subset solely from its index.
For simplicity, I will just assume $\Omega=\{0,\dots,m-1\}$ so that the states have a natural ordering to them.
With this, you can think of the set of size-$n$ subsets of $\Omega$ as length-$n$ strictly increasing sequences of numbers in $\Omega$, and you can order these lexicographically. This gives you one direction of the enumeration.
Now, we need only go backwards.
If we fix the first number of a length-$n$ increasing sequence to be $k$, then the remaining numbers have to fit in $\{k+1,\dots,m-1\}$---a set of size $m-k-1$, which means that there are ${m-k-1\choose n-1}$ length-$n$ increasing sequences which start with $k$ for any $0\leq k\leq m-1$.
This is the key for us to reverse-engineer the state from the index.
If we look at the subproblem of a length-$(n-1)$ increasing sequence of states in $\{k+1,\dots,m-1\}$, we can re-index everything by shifting down by $k+1$ and solving the recursive problem.
In summary, we can define a procedure $\def\getState{\operatorname{getState}}\getState(i,n,m,j)$ which prints the $i$th state in the lexicographical ordering of size-$n$ subsets of the set $\{j,\dots,j+m-1\}$ as follows:

*

*if $n=0$, quit

the only size-$0$ subset of a set is empty



*otherwise, let $k$ be maximal with $p := \sum_{j\leq k}{m-j-1\choose n-1}\leq i$ and print $(j+k)$

this finds the smallest element of the state



*recursively call $\getState(i-p, n-1, m-k-1, j+k+1)$

the remaining problem is to find the $(i-p)$th state in the lexicographical ordering of the size-$(n-1)$ subsets of the set $\{j+k+1,\dots,j+m-1\}$

You can use memoisation to speed up the computation of the binomial coefficients (using Pascal's triangle).
With the above procedure, the answer to your original question will be $\getState(i,n,m,0)$.
A: Out of the $\binom mn$ possible $n$-element subsets of the $m$ squares, $\binom{m-1}{n-1}$ have a piece on the last square, and $\binom{m-1}{n}$ don't.
So you can do the following:

*

*If there is no piece on the last square, use this algorithm recursively for the arrangement of $n$ pieces on the first $m-1$ squares. This gives you a number between $0$ and $\binom{m-1}{n}-1$.

*If there is a piece on the last square, use this algorithm recursively for the arrangement of $n-1$ pieces on the first $m-1$ squares. This gives you a number between $0$ and $\binom{m-1}{n-1}-1$. Then, add $\binom{m-1}{n}$ to it, getting a number between $\binom{m-1}{n}$ and $\binom mn - 1$.

As a base case for this algorithm, whenever $m=n$ or $n=0$, there is only one possible arrangement, and you should give it the number $0$.

Actually, if we look carefully at the recursive algorithm above, we can "unroll" it. Note that we only have one place where we modify the number we get: when the $n^{\text{th}}$ piece is on the $m^{\text{th}}$ square, we add $\binom{m-1}{n}$ to the number. (We can simplify this rule by numbering the squares $0, 1, 2, \dots, m-1$, so that the $m-1$ in $\binom{m-1}{n}$ is the number of the last square.)
So if the squares are numbered $0, 1, 2, \dots, m-1$ and the pieces are located on squares $0 \le m_1 < m_2 < \dots < m_n \le m-1$, then the algorithm above will ultimately produce the value
$$
    \binom{m_1}{1} + \binom{m_2}{2} + \dots + \binom{m_n}{n}
$$
and we can just output that directly. (But without the recursive algorithm, it would be super unclear why that worked.)
