Virtual Hat
Toss a bunch of names in the hat, and let everyone pick one!
Names: (1 per line, please)

List # (Leave the list # blank and I'll make one up)

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:

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


austindavid.com > flotsam
Comments? Updated Tue, 11 Jun 2013 17:56:06 -0600