# 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).

• You won't be alive when this finishes, but hopefully you will still be alive at the next power cut :-) Jun 17, 2022 at 13:42
• Your goal is unclear. Do you want to enumerate all numbers of $k$ ones, or count the number of ones in a given number ? Or generate random numbers with $k$ ones ?
– user16034
Jun 17, 2022 at 18:39
• @YvesDaoust My goal would be the first option: enumerating all numbers up to a certain cut-off number which all have a population count of $k$ (i.e. $k$ ones). Jun 19, 2022 at 7:46

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 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.

• Apologies for responding so late, I haven't had the time yet to write this out in code, I'll keep you posted! Jun 10, 2022 at 17:35
• I've read the original paper by Tom Cover, but I struggle to wrap my head around how the inverse function works, that is, to get the word W by its index. Would you mind elaborating on that part a bit? Jun 17, 2022 at 11:42
• see my edit please Jun 17, 2022 at 13:32