document updated 17 years ago, on Apr 26, 2007
Thoughts
One way to GUARANTEE that a machine shuffles completely randomly is to build a machine that isn't
designed to shuffle, but is instead designed to precisely reorder a deck of cards based on a
computer's commands, and it's the computer that originally decides what the order would be (where
it's the computer guaranteeing that the deck is random, since the computer can do 1000 virtual
riffles in a blink of an eye). eg. it becomes more like a Rubik's Cube or Towers of Hanoi solution
problem than anything else. The computer could then, of course, optionally seek to minimize the amount of
physical movements required to reach the goal state.
For instance, the simplest way to shuffle 52 cars would be to have something like 30 shelves --
but allocate those shelves so that they're at the bottom of a run of strictly-increasing cards...
so if we had a mechanism that let us first place card #52 in any shelf, then card #51 in any shelf,
then card #50, etc... (which means that within any single shelf, they have to be put in order) that
we could fully shuffle the entire deck in one pass.
13
17
----
5
15
----
2
34
----
31
52
----
18
23
50
----
4
35
----
29
----
7
38
49
----
45
----
24
40
----
32
----
3
14
----
1
48
----
10
19
----
6
36
41
----
26
----
13
42
----
37
----
16
----
11
44
----
9
51
----
22
30
46
----
27
47
----
20
43
----
33
----
25
----
21
28
----
8
39
In this example, we needed 28 shelves to do a totally random shuffle. Unfortunately, the maximum
numer of shelves we'd need is 52 (when the cards are sorted exactly in reverse order), and the
minimum number of shelves is 1 (when the cards are sorted exactly in normal order). When running a
simulation of shuffles, the average was consistently 26.5 shelves.
HOWEVER, note that the bad scenarios are pretty rare. The worst case (that 52 shelves are
needed) has a 1/52! chance of happening. The chance that we need either 52 or 51 shelves is
(1+51)/52!. etc. It's pretty low. In a simulation of 10,000 shuffles of a 52-card deck, it needed a maximum of 35
shelves to sort.
Can place the card on the top or bottom of any shelf
eg. making a "sandwich" as this mentions.
In a quick simulation... doing 10,000 sorts of a 52-card deck resulted in an average of 17.65 shelves being needed, a minimum of 11, and a maxmimum of 24 shelves.
Is the worst-case then 1/2 of the cards (26 shelves) since the worst case is alternating cards? eg. 52, 1, 51, 2, 50, 3, 49, 4, 48, 5, ...?
Simple deck cutting?
Is it possible to use the mechanism that appears on just about every cheap card-shuffler
Future questions
- how many shelves do we need if we do the above step *twice*? (and what's the strategy for dividing things up into shelves then?)
- how many shelves do we need if we don't break the whole deck up first, then group together, but
instead break up maybe 5, then group them together, then break those up, and break up 5
more, then group them all together, etc... how many shelves then?
Physical
A cheap way to make an elevator of shelves might be to take some technic gear racks, a bunch of the cheap
plastic sleeves, cut the bottom end off, split the middle of the top, and then glue it into the gear
rack (possibly with some paperclips wedged in there as rails, with the plastic sleeve coming up the
sides to make sure the card doesn't catch on the back side.
Casino shufflers