3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Must the cards be distinct? Or can you select the same card more than once? $\endgroup$ – Dr Xorile Jan 1 at 22:38
  • 1
    $\begingroup$ Also, can you distinguish the dice? Eg a red dice and a blue one? $\endgroup$ – Dr Xorile Jan 1 at 22:40
  • 3
    $\begingroup$ Shuffle the deck and deal off the first $x$ cards. 0 throws! $\endgroup$ – Dr Xorile Jan 1 at 22:57
  • $\begingroup$ Yes, that's what most suggest, but there are cases where players don't like shuffling it (they're allowed to have it ordered so it is easier to retrieve cards from it). In addition, the back of the cards in that deck may be marked. $\endgroup$ – Shuri2060 Jan 2 at 13:06
  • $\begingroup$ If you were to roll multiple dice at the same time, then yes they are distinguishable. The selected cards must be distinct. $\endgroup$ – Shuri2060 Jan 2 at 13:36
3
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ I almost posted something very similar to this, but gave up when it got to "Now convert to the Combinatorial number system in order to pick the 3401st choice of the 5005 ways to choose 6 from 15."; while possible by hand, it's not trivial (14-C-5 = 2002 start with A, ...) I guess a pad with Pascal's triangle would help. $\endgroup$ – Jonathan Allan Jan 2 at 19:37
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If $N=14$, step 1 gives you two piles of seven cards, so in step 2 you have $c=7$. In step 2 you will then never pick the seventh card using a 6-sided die. If $N=13$, then step 1 splits it into four piles, which makes the $\mod p$ part of step 1 problematic (you want $p|6$ else pile $1$ is more likely to be chosen that pile $p$) Both problems can be fixed by splitting into 3 piles. In step 2 the "go back to step 1" rule is supposed to ensure uniform distribution. However, this only works correctly if you apply it to every pile and not use the $\mod c$ procedure. $\endgroup$ – Jaap Scherphuis Jan 2 at 6:38
  • $\begingroup$ Woops yeah need to change this $\endgroup$ – Shuri2060 Jan 2 at 13:04
  • $\begingroup$ Fixed, I hope.. $\endgroup$ – Shuri2060 Jan 2 at 13:31
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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