?

Log in

No account? Create an account
Choosing 4 out of 12 items with 3d8 - onigame [entries|archive|friends|userinfo]
onigame

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Choosing 4 out of 12 items with 3d8 [Jul. 28th, 2008|12:39 am]
onigame
The number of ways to choose 4 items out of a set of 12 items is 495.

The number of results you can get by rolling an eight-sided die 3 times is 512.

Therefore, theoretically, if you're trying to choose 4 out of 12 items, you can roll an eight-sided die three times, and 96.6796875% of the time you won't need to re-roll.

However, it's not particularly obvious how to map 495 of the 512 results onto choices of 4 items. Yes, you could have a massive look-up table with 495 rows, but that's a bit hard to carry around in your pocket.

So, I've come up with the following little "rule"... unfortunately, it's much more complex than I had hoped. Can anyone do better?

Let's call the 12 items you're trying to choose ABCDEFGHIJKL. Split them into two halves,
ABCDEF and GHIJKL. Generally, we're going to have the first roll of the die tell us how
many to choose from each half, with the other rolls telling us which ones.

Now, we'll roll the die three times, let's say the values are X, Y, and Z. Then:

If X == 1, then we're going to choose three items from ABCDEF, and one item from GHI.
If X == 2, then we're going to choose three items from ABCDEF, and one item from JKL.
If X == 3, then we're going to choose three items from GHIJKL, and one item from ABC.
If X == 4, then we're going to choose three items from GHIJKL, and one item from DEF.
If X == 5 through 8, then we'll either choose two items from both halves, or all items from the same half.


For the case of X == 1 through 4, we need to choose 3 out of a group of 6, and 1 out of a group of 3. Let's call the group of six MNOPQR, and the group of three STU.

If Y == 1 through 6, then we'll choose MNO based on the bit representation of Y. To wit:
Y == 1, choose --O.
Y == 2, choose -N-.
Y == 3, choose -NO.
Y == 4, choose M--.
Y == 5, choose M-O.
Y == 6, choose MN-.


After that, we'll have three choices of the group PQR (either 1 or 2 items, based on how many of MNO were chosen), and three choices of the group STU. We'll use the roll Z to put among those 9 choices -- simply put Z in base three, and choose among PQR and STU appropriately (using the mapping 012).

Since that's 8 outcomes to choose among 9 results, one will be leftover, namely, P and S. So let's use those for the case Y == 7:
Y == 7 and Z == 1: --O -QR S--
Y == 7 and Z == 2: -N- -QR S--
Y == 7 and Z == 3: -NO P-- S--
Y == 7 and Z == 4: M-- -QR S--
Y == 7 and Z == 5: M-O P-- S--
Y == 7 and Z == 6: MN- P-- S--
Y == 7 and Z == 7: MNO --- S--
Y == 7 and Z == 8: --- PQR S--


This leaves four cases left, and we'll map them to when Y == 8:
Y == 8 and Z == 1: MNO --- -T-
Y == 8 and Z == 2: MNO --- --U
Y == 8 and Z == 3: --- PQR -T-
Y == 8 and Z == 4: --- PQR --U


In the case where Y == 8 and Z > 4, reroll.

Now, when X is 5 through 8, we'll be choosing two items from each half (or four from the same half). It turns out there are 15 ways of choosing two items from a group of 6 (or four from a group of 6), and conveniently 15 just a little bit less then twice 8. I haven't found a good way to map numbers from 1 to 15 onto the 15 ways, so here's one that's as good as any:

MN----  1
-NO---  2
--OP--  3
---PQ-  4
----QR  5
M--P--  6
-N--Q-  7
--O--R  8
M-O---  9
-N-P-- 10
--O-Q- 11
---P-R 12
M---Q- 13
-N---R 14
M----R 15


So, now all we need are two numbers from 1 to 15. That's pretty easy, since we have the rolls Y and Z, which range from 1 to 8. Now use X to distinguish:

If X == 5, take Y and Z exactly.
If X == 6, add 8 to Z.
If X == 7, add 8 to Y.
If X == 8, add 8 to both Y and Z.


Now Y and Z are all in the range 1-16. So:

If both Y and Z are in the range 1-15, use Y to choose two items from ABCDEF and Z to choose two items from GHIJKL.
If Z == 16, then use Y to identify two items from ABCDEF; then choose the other four.
If Y == 16, then use Z to identify two items from GHIJKL; then choose the other four.


Finally, if both Y and Z are 16 (you rolled 8, 8, 8), then reroll.
LinkReply

Comments:
From: thedan
2008-07-28 01:16 pm (UTC)
The 60/60/60/60/255 split at the beginning is pretty ingenious. I'll have to think later about improvement methods, but I suspect that step wants to be preserved.
(Reply) (Thread)
[User Picture]From: onigame
2008-07-28 04:41 pm (UTC)
Ed Pegg missed my point by pointing me to Don Knuth's algorithms for generating a list of combinations.

The point here isn't to find an algorithm that generates all lists -- that's easy and then reduces to the look-up table situation.

What's not trivial is a mapping that is easy enough that a human can do it via random access -- e.g., know which subset is number #241 without needing
to calculate the first #240.

Let me give a simpler example to show the sort of goal I'm striving for: You want to choose an ordered set of 3 out 9 items (504 possibilities) with 3d8 (512 possibilities). Here's something that any human can do:

0. Number the nine items 1-9.
1. Roll the die twice (XY).
2. If you roll double-8's, re-roll.
3. Roll the die a third time (Z).
4. If X = Y, choose 9 for the first item; otherwise choose X.
5. Renumber the remaining items 1-8.
6. Choose Z for the second item.
7. Renumber the remaining items 1-7.
8. If X >= Y, choose Y for the third item.
9. If X < Y, choose Y-1 for the third item.

No general-purpose enumeration algorithm is going to come up with
this, since it is rather specialized for the case of generating 3 out
of N+1 items with three rolls of an N-sided die.
(Reply) (Thread)
From: (Anonymous)
2008-08-25 10:55 pm (UTC)

Choosing 4 out of 12 items with 3d8

After playing around with this for a while, I stumbled upon a mapping to the integers.
Let mCn be short for m choose n.
Map the 12 elements to {0,1,2,...11}.
Take the subset {a,b,c,d} to aC1+bC2+cC3+dC4
Take the roll XYZ to X*64+y*8+Z. (the rolls are from {0,1,...7}

Thus the set {0,2,5,8} corresponds to
0C1+2C2+5C3+8C4 = 0 + 1 + 10 + 70 = 80 (corresponding to the roll 120)
The subset #241 (out of 0 through 494)
is 241 = 10C4 + 31 = 10C4 + 6C3 + 11 = 10C4 +6C4 + 5C2 + 1
= 10C4 + 6C4 + 5C3 + 1C1, the subset is {1,5,6,10}
and the corresponding roll is 331.
To me, the computation of the binomial coefficients doesn't seem any more complicated than the algorithms listed, and has the advantage of being easily generalizable, to
{a1,a2,...,ak} <-> a1C1+a2C2 + ... +akCk.

Further searching reveals that it's Theroem L in Section 7.2.1.3 Knuth (AOCP, Vol. 4), equivalent to one of the machine algorithms (Algorithm L), and he lists a 19th century reference.

jhr @ RHIT

(Reply) (Parent) (Thread)
[User Picture]From: devjoe
2008-07-28 11:12 pm (UTC)
Here's a way to make that table of 15 ways to choose 2 of 6 objects a bit easier to handle. Number them 0, 1, 2, 4, 8, and -15, and if your number is Q, choose the two that add to Q or -Q. 0+1, 0+2, 1+2, 0+4, 1+4, 2+4, 8-15, 0+8, 1+8, 2+8, 4-15, 4+8, 2-15, 1-15, 0-15. Since the numbers all sum to zero, when you need to take the other four numbers instead, you're still taking a set that adds to Q or -Q. It makes it a little bit of a puzzle (uhhh, which two add to +/-11?) but instead of a table of 15 cases, you only have to remember the sequence 0, 1, 2, 4, 8, -15 which is just the powers of 2 bracketed by 0 and -15.
(Reply) (Thread)
[User Picture]From: onigame
2008-08-07 12:33 pm (UTC)
That's amazingly cool. Where did you come up with that?
(Reply) (Parent) (Thread)
[User Picture]From: devjoe
2008-08-07 03:46 pm (UTC)
I figured it out myself, starting with the idea of numbering them so that the sums of all the pairs would be different, and playing with the numbers until I found something that worked. I was initially thinking of Golomb rulers, though this works rather differently, so I went on experimenting with numbers. I saw that I could not have them all different and consecutive, but when looking at the pattern of numbers I was getting, I saw that I could make it work with the negative as given above.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-07-28 11:27 pm (UTC)
I take it you can't upgrade to 4d12.
(Reply) (Thread)
[User Picture]From: onigame
2008-07-29 08:49 am (UTC)
4d12 is inefficient. You should at least use 4d11 if you're going to do that tack.
(Reply) (Parent) (Thread)