Title: Pick a secret Santa assignment in C#

In a secret Santa party, you put everyone's names in a hat and people draw from the hat. Each person becomes the secret Santa for the person they draw and gets that person a present for the party. To keep things fun, no one should be their own secret Santa.

A permutation of items where none of the items is permuted into its own original position is called a derangement. Basically the secret Santa problem is to find a derangement of the people who will be at the party.

When you draw from a hat, you need to figure out what to do if you draw your own name. You could just draw a new name and then put your name back in the hat, but that has a couple of problems.

First, it reduces the anonymity. If you draw your own name, then everyone (including you) knows that none of the people who drew before you is your secret Santa. In the worst case, suppose you're the second-to-last person to draw and you get your own name. Then you know that the last person is your not-so-secret Santa.

A second problem occurs if you are the last person and you draw your own name. In that case you can't draw a new name.

Another way to deal with the case of someone drawing his or her own name is to put all of the names back in the hat and start over. You then repeat until you get a valid draw. That's the approach this example takes in the following code.

// Generate a random derangement. private int[] SecretSantaAssignment(int N, out int num_tries) { // Make an array to hold the assignment. int[] assignments = new int[N]; for (int i = 0; i < N; i++) assignments[i] = i; // Try random permutations until we find one that works. //Console.WriteLine(); num_tries = 0; for (; ; ) { // Randomize the assignment array. num_tries++; assignments.Randomize(); // Display this permutation. //for (int i = 0; i < N; i++) // Console.Write(assignments[i].ToString() + " "); //Console.WriteLine(); // If this is an invalid assignment, try again. bool is_valid = true; for (int i = 0; i < N; i++) { if (assignments[i] == i) { is_valid = false; break; } } // See if this is a valid assignment. if (is_valid) break; } return assignments; }

The method first creates an assignments array containing the peoples' numbers 0, 1, 2, ... The value assignments[i] will eventually contain the index of the person assigned to person i. In other words, person i is the secret Santa for person assignments[i].

Next the code enters a loop that runs until the method finds a valid assignment. Inside the loop, the code uses the Randomize extension method to randomize the array. To see how that method works, see the post Make extension methods that randomize arrays and lists in C#.

The method then checks the assignments array to see if it has found a valid assignment. If the assignment is okay, the code breaks out of the infinite loop and returns the assignment it found.

Randomizing the array is quite fast. The only remaining question is, "What are the odds that you'll pick a valid assignment?" There are lots of ways a permutation of N numbers might have one or more numbers permuted to its original position, so you might worry that you'll have to repeat the loop many times.

While it is true that many permutations are invalid, there are a LOT of permutations in total, so the odds of you finding a valid derangement are pretty good. You might need to randomize the array a few times to get a derangement, but you probably won't have to do it too many times.

In my next post, I'll explain how you can calculate the number of derangements so you can see that the odds of picking a good arrangement are pretty good. I'll also show how you can enumerate all of the possible derangements, at least for small parties.

Download the example to experiment with it and to see additional details.