Generating the n-th number with k bits set, is it possible?

Question

Generating numbers with $k$ bits set for a poker simulation

Context

I'm trying to generate all possible Texas Hold'em games for $p$ players, which means there will be at most $2 \cdot p + 5$ cards at play.

To make things a little bit easier, I figured that I could use a 64-bit number to represent each of the cards in a standard 52-card deck (from $2^0$ through $2^{51}$) and represent a full game as the sum of any $2 \cdot p + 5$ distinct 64-bit numbers.

For example, if in my ordering, the suit order is clubs, diamonds, hearts, spades, then $1$ would be the ace of clubs ($1♣$), $2$ would be the ace of diamonds ($1♦$), and so on. At the end of the deck will be the king of spades ($K♠$) with a numerical value of $2^{51} = 2\,251\,799\,813\,685\,248$ (quite big). This way, the number $2^{51} + 2^1 + 2^0$ uniquely represents a player's hand of $K♠1♦1♣$.

Example with two players

Plugging in $p=2$ yields a total of $9$ cards at play for a two-player Texas Hold'em game.

This means that any sum of nine distinct numbers from the set described above would represent a valid game of Texas Hold'em poker with two players. For example, the decimal number $511_d$ in binary is $1\,1111\,1111_b$ and the number $991_d$ in binary is $11\,1101\,1111_b$.

What I've tried

My initial strategy was to iterate over all 64-bit numbers, checking each number to see if it has $9$ bits set with an algorithm I found online, but I realized I probably wouldn't be alive anymore by the time it finished.

I then thought that maybe I could generate a few terms of each $k$ algorithmically and then fit a polynomial through them to "predict" the next terms, but that was a dead end as well.

So I was wondering if there exists a closed-form expression to yield the $n$-th number that has $k$-bits set to $1$ in its binary representation ($k=9$ in the two-player example).

Answer 1

This is called Enumerative Coding and was introduced by Tom Cover. Consider a word $W$ that is $n$ bits long, where the one bits are in locations $x_k, \ldots, x_1$ with $x_k>x_{k-1}>\cdots>x_1$ and the locations are labelled from $0$ to $n-1.$

The position of this word in the lexicographic ordering of all words with exactly $k$ $1$ bits set is an integer which we conveniently start at $0$ (due to the formula used):

$$\textrm{Position}(W)=\sum_{1 \le i \le k} { x_i \choose i}.$$

So, for example, for a 6-bit word with $3$ bits set:

$$\textrm{Position}(000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$ $$\textrm{Position}(001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$ $$\textrm{Position}(111000) = { 5 \choose 3 } + {4 \choose 2 } + {3 \choose 1} = 19$$

Note that the binomial coefficient $\binom{n}{k}=0$ if $n<k.$ The first word $000111$ has index zero and the last word $111000$ has index $19.$ There are $\binom{6}{3}=20$ such words so this checks out.

You would apply this with $n=64,$ and $k=9,$ etc.

Edit: Inverse mapping

For the inverse, note that the sequence $$ {x_i \choose i },\quad 1\leq i\leq k $$ is increasing in $i$ (being a subsequence of the diagonal of the pascal's triangle).

So given the position, since you know $k$ just find the largest quantity of the form $x \choose k$ which obeys $${x \choose k} \leq \textrm{Position}(W).$$ The value of $x$ which is the largest is your $x_k.$ Then find the largest $x$ which obeys $$ {x \choose k} + {x_k \choose k} \leq \textrm{Position}(W) $$ which is your $x_{k-1},$ and so on recursively, for $k$ steps.