Randomly selecting cards using 6-sided dice

Question

There is a pile of $5\leq N\leq15$ cards.

$x=3$ or $6\leq N$ cards need to be randomly chosen from this pile (uniform distribution).

To do this any number of $6$-sided dice can be rolled any number of times.

What are efficient methods of doing this? Or if it's not possible to do better than the method I've listed as an answer, why?

---

Notes:

• Efficiency $E_1$ is the expected number of individual dice rolls needed.
  Efficiency $E_2$ is the expected number of rolls needed (simultaneous rolls count as 1 roll).
  
  As this puzzle arises from a practical situation where one may or may not have multiple dice, both of these measures of efficiency are useful to take into account.
  
  Also note in practice, a maximum of $\approx3$ dice can be rolled at the same time.

• $x=6$ most of the time, especially when $N\geq10$.

• $N\approx 15$ most of the time, so being able to find more efficient methods for any of the cases when $N\geq10$ is desirable.

---

If you're wondering, this problem arises from a common occurrence when using the card Pot of Indulgence in the card game Yu-Gi-Oh, hence the specific numbers, etc.

Answer 1

You want to uniformly choose one out of $n=\binom{N}{x}$ possibilities. In essence you are therefore trying to emulate an $n$-sided die using as few rolls of a $6$-sided die as possible.

Here follows a pretty efficient and very generic way to do this.

Firstly, it is much easier to use zero-based numbering on the die, i.e. have a die with the values $0$ to $5$.

While throwing the die, you have to keep track not only of the values thrown but also of the range of values they could have been. So after the first die roll you not only know the outcome, but also that it could have been any one of $6$ values. Let $r$ be the range, i.e $r=6$ after the first roll. Let $v$ be the value of the first roll (in range $0\le v \le 5$).

1. Roll the first die. This gives $r=6$, and $v=d$ is the die value.

2. If $r<n$, the range is less than the number of options we are choosing from, then roll another die. Multiply the range by $6$ to get the new range ($r \leftarrow 6r$). Multiply the current value by $6$ and add the rolled die to get the new value ($v \leftarrow 6v+d$).

3. Repeat step 2 until $r\ge n$.

4. Write $r=nq+r_2$ for some quotient $q>0$ and remainder $0\le r2<n$. If $v<nq$ then let $k=v\%n$ (where $\%$ denotes the modulo operation) and stop, choosing the $k$th of the $n$ options. If $v\ge nq$, then set $v \leftarrow v-nq$ and $r \leftarrow r_2$ and go back to step 2.

Example:
Suppose you want to choose $2$ out of $5$ cards. $n=\binom{5}{2}=10$.

• First roll gives $5$. Set $v=5$, $r=6$.
• $r<n$ so do another roll.
• Second roll gives $2$. Set $v=6*5+2=32$, and $r=36$.
• Now $r\ge n$. If $v$ were in range $0..9$ we'd choose $k=v$, if $v$ were in range $10..19$ we'd choose $k=v-10$, and if $v$ were in range $20..29$ we'd choose $k=v-20$. Unfortunately $v$ lies in the remainder interval $30..35$, so we set $v=32-30=2$ and $r=36-30=6$.
• $r<n$ so do another roll.
• Third roll gives $5$. Set $v=6*2+5=18$, $r=36$.
• Now $r\ge n$. As $v$ is in the range $10..19$ we choose $k=v-10=8$, and can stop rolling.
• Finally, remember that $k$ is zero-based (i.e. range $0..9$), so we must choose the ninth of the ten ways to choose 2 out of 5 cards. If the cards are A,B,C,D,E and our choices are ordered alphabetically, the ninth choice is C&E (four start with A, three with B, so we need the second choice that starts with C).

Answer 2

One approach would be to write a list of all possible combinations of size x. Then have a look up table against a number of throws of the dice (depending how many are listed). You obviously want to get it close to the number of possible throws, because if you make a throw that's not on the list, you will need to re-throw.

You can also make one of the dice act like a 2-sided or 3-sided dice if necessary to get the number of possible dice throws to be $/gtrapprox$ the number of possible combinations.

This could be done with 4 throws for $x=3$ and $N=15$ and 5 throws for $x=6$ and $N=15$. But obviously this requires a look up table.

An alternative to this is to assign each card a number. How you do this will depend on $N$. For $N\leq 6$ you will use 1d6. For $N=15$ you will use d6 x d3. So say you have a blue dice and a red one. Then map the red one to 1,2, or 3. Map the blue one to 1-5 (by simply rethrowing if a 6 comes up). And then assign each card a pair of numbers.

Having done this, you can pick a card with uniform probability in one throw (or sometimes a few more if you hit one of the unassigned numbers and have to re-throw). Then just do this $x$ times.

Answer 3

This method generally requires at least 6/12 rolls (or 3/6 if allowing 2 dice to be thrown at the same time). I’m hoping for something much better ($\leq 4$ rolls) to be possible as this consumes quite a bit of time.

---

Method: Select each card one at a time. Repeat the following for each card selection.

Step 0: If $N\leq6$ skip to Step 2.

Pick the smallest number from the below list greater than $N$ and let $c_1, c_2$ be the listed factors of that number.

$6=2\cdot3$
$9=3\cdot3$
$12=2\cdot6$
$18=3\cdot6$

Divide the cards into $c_1$ piles as evenly as possible.

Step 1: Roll 1st dice (assign $d_1=$ result).

Let $n_1=d_1\pmod{c_1}$.

Step 2: Roll 2nd dice (assign $d_2=$ result).

Let $n_2=d_2\pmod{c_2}$.

Select the $n_2$th card in the $n_1$th pile. If that card doesn't exist, go back to Step 1. (If piles were of equal size, repeat Step 2 instead).

Answer 4

First determine the number of possible combinations $C$ this is $n!\over{r!(n-r)!}$ for selecting $r$ cards from a deck of $n$.

Roll sufficient dice $d$ to get $6^d \geq C$

compute the result in base 6 (first die worth 0,1,2,3,4,5 second worth 0,6,12,18,24,30 etc. )

divide the result by the largest integer $q$ such that ${6^d\over{q}} \geq C$ rounding down to get $e$

if $e$ is less than $C$ use the combination represented by $e$ in a sorted list of all combinations

having a printed list would be helpful there's 360360 possiblie combinations of 6 or 7 from 15

in some cases it may be advantageous to roll an extra die than is required so that by using a a larger $q$ the chance of $e \geq C$ requir1ng a re-roll can be reduced.

worse case is 6 from 15 requiring 8 dice with a 16% (E=9.58) retry or 9 dice with a 4% retry (E=9.33) choice between these two probably depends on if you'll accept 5≈3

This is similar to Dr Xorile's method, except that the result reduction is done on the combined roll result, allowing reduction ratios other than $2^x3^y$ meaning a closer approach to ideality and so reduced re-roll probability.