Toss a bunch of names in the hat, and let everyone pick one!
Welcome Google users!
I hope you enjoy this whimsical page. If you find this fun or
useful (or neither), drop me a note over at
Google+.
The Algorithm
The "virtual hat" follows a specific series of steps to draw all names
from the hat:
- Each person draws in turn, starting with the first person in the list.
- On a person's turn:
- he shakes the hat
- he removes one name from the hat
- If anyone draws his own name, or if a "loop" is detected, the
draw is considered "unfair" and everyone draws again.
List Number
There are about 21 trillion ways to draw 17 names from a hat (for you
math types, it's
n-1!).
The "virtual hat" simulates shuffling
(shaking the hat to stir names) using a random number generator, which
is a fancy way to say that every shuffle is a little bit different, but
they all start with a "list number."
If you just toss names into the hat without providing a list number, the
virtual hat will make one up (up to 4 digits). The "list number", is
printed above the output.
The list number can be used to identify a drawing; the same list number
will always produce the same draw results. Different list numbers aren't
guaranteed to produce different results, however. There are only 120
ways to draw 6 names (far smaller than the space used for list #).
Unfairness
When a group of people draw names from a hat, sometimes the last person
to get the hat will have to draw his own name; this is an unfair draw.
When the "virtual hat" detects this condition, it will simply draw all
names again (after shuffling the hat, by adding 1 to the list number).
Loops
A 'loop' occurs when a subset of people draw each other's name. For instance:
Alice => Bob
Bob => Carol
Carol => Alice
Doug => Edward
Edward => Frances
Frances => Doug
This group has a loop with list #s 1, 2, 4-18, and many others
The group Alice, Bob, Carol does not include the rest of the participants.
If this condition is detected, the draw is considered invalid and is run
again for the next-higher list number; the process repeats until a draw
is valid.
A loop is detected by traversing the list in order -- in the above example,
Alice -> Bob -> Carol -> Alice. If we manage to find all the names
before we find a repeat, then the draw is valid (no loops). This is a
variation of the "tortoise and hare" algorithm for detecting loops in a
linked list of unknown size.