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.
