Consider a standard Secret Santa/gift exchange game draw. We have a pool of $n$ people, each of whom is supposed to be assigned another member of the pool to find a gift for, without the recipient knowing whom they've been assigned to. Essentially, we would like to generate a random derangement without leaking too much (or ideally, any) information about it to the participants, beyond the name of the person they're assigned to.
Obviously we could use a trusted third party or online organizer to do this, but that's not much fun to do at a party, so it'd be better if we could use some method that could be implemented by hand, solely by the participants.
While everyone should ideally have an equal chance of getting assigned to everyone else, it's probably okay if our algorithm is nonuniform over cycle types. In fact, it'd be kind of neat if there was a way of doing this that always generated $n$-cycles, since that would also let you play a self-running Assassin game.
There are two obvious algorithms for doing this:
1) Everyone pulls a name out of a hat, and checks to see if they've drawn their own name. If so, everyone puts the names back and starts over.
This works fine (it's essentially the rejection algorithm for generating random derangements), but is kind of tedious. And there's a tendency for it to degenerate into:
2) Everyone pulls a name out of a hat one by one. If you get your own name, put it back and draw again.
This can fail if the last person draws their own name (at which point you'd have to start over from the beginning). It also leaks information. If someone puts their own name back, that means none of their predecessors can have drawn it; in the extreme case, if person $n-1$ puts their own name back, it's guaranteed to be drawn by person $n$. Additionally, it's not actually uniform, as discussed in this answer.
One could also try to implement something like Sattolo's algorithm to get an $n$-cycle, or the algorithm in this paper to get a general derangement, but I haven't been able to come up with a way to do that by hand without leaking information.
Is there any way of doing this that works better than algorithms 1) or 2), at least arguably? (i.e., can be implemented by hand using common household ingredients faster than algorithm 1), and is more uniform and/or less leaky than algorithm 2)?)
Best Answer
I recommend you watch The Assassin Problem (James Grime) which deals with exactly this problem. James Grime posed the question to his viewers on his Youtube Channel: SingingBanana and asked for viewer responses to try to come up with an easy to understand and easy to implement solution which avoids the potential for cheating and leaking knowledge.
Their favorite solution was submitted by a user named GrandDizzy and it goes as follows:
$\bullet$ Take a stack of index cards and on each card write a person's name twice (once on the left in blue and once on the right in red)
$\bullet$ Shuffle that deck of index cards face down.
$\bullet$ Take a pair of scissors and cut the cards down the middle(top-down cut with scissors, not like a "cut" in shuffling). What is left are two stacks of cards, one with blue names and one with red names, both in the same order.
$\bullet$ Take the top card from the red stack and move it to the bottom of it's stack.
$\bullet$ Now, you can remove the top card of each stack and staple them together (blue on bottom, red on top)
$\bullet$ Mix these and lay them out. The person takes the stapled set with their name showing, and their target is the person's name which is hidden stapled below theirs.