Draw Names from a Virtual Hat

Names Draw results

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.

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 reshuffling the hat).

Loops / cliques

A 'loop' occurs / clique exists when a subset of people draw each other's name. For instance:
  • Alice => Bob
  • Bob => Carol
  • Carol => Alice
  • Doug => Edward
  • Edward => Frances
  • Frances => Doug
The clique 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; the process repeats until a draw is valid. To avoid blowing up a browser, it will give up after 500 tries. Please LMK if you see that.

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.