1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ You won't be alive when this finishes, but hopefully you will still be alive at the next power cut :-) $\endgroup$
    – gnasher729
    Jun 17, 2022 at 13:42
  • $\begingroup$ 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 ? $\endgroup$
    – user16034
    Jun 17, 2022 at 18:39
  • $\begingroup$ @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). $\endgroup$ Jun 19, 2022 at 7:46

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Apologies for responding so late, I haven't had the time yet to write this out in code, I'll keep you posted! $\endgroup$ Jun 10, 2022 at 17:35
  • $\begingroup$ 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? $\endgroup$ Jun 17, 2022 at 11:42
  • 1
    $\begingroup$ see my edit please $\endgroup$
    – kodlu
    Jun 17, 2022 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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