Title: Calculate the number of secret Santa permutations in C#

The example Pick a secret Santa assignment in C# picks a valid permutation of the people so no one is mapped to themself. Such a permutation is called a derangement. See that example for details.

The number of possible derangements for N items is called the subfactorial of N and is written !N, D_N, d_N, or N¡. This example calculates the subfactorial and shows how to enumerate all of the possible derangements.

Calculating !N

It turns out, calculating the subfactorial function is quite easy, although understanding it isn't completely trivial.

Suppose you have N people. There are N - 1 ways person 1 can pick another name without messing up the derangement. (Person 1 can pick any name but their own.) The total number of derangements will be N - 1 times the number of possible combinations given that person 1 has made a choice.

Suppose person 1 picked person p and consider the person that person p picks next. There are two cases.

Case 1: Suppose person p picks person 1, so basically person 1 and person p swapped. In that case, the number of possible remaining derangements is the same as the number of derangements with persons 1 and p removed from the list. In other words, simply generate the derangements for the original list with persons 1 and p removed. The reduced list contains N - 2 people so it has !(N - 2) possible derangements.

Case 2: Suppose person p doesn't pick person 1. You can think of the derangement problem as mapping N items to N items where no item can be mapped to its original position. The following picture shows the initial mapping after person 1 is mapped to person p.

Remove item 1 from the top (because it has already been used as a secret Santa) and item p from the bottom (because it has already been used as a gift recipient). Then move item 1 on the bottom below item p on top as shown in the following picture.

Now you just need to calculate the number of derangements possible in this new arrangement. In this mapping, each item on the top has one position on the bottom that is forbidden to it: the position directly below. For example, item 2 cannot map to item 2. The only weird one is item p can not map to item 1. But in Case 2 we are assuming that item p doesn't map to item 1, so that's okay.

This arrangement contains only N - 1 items so there are !(N - 1) derangements. (Note that you don't actually need to perform the mapping. That would be a hassle. We just need to know that it has !(N - 1) derangements.

Putting all that together gives the following recurrence relation.

Where !0 = 1 and !1 = 0.

You can use that relation to recursively calculate the number of derangements. The following code shows how this example calculates the number of derangements.

// Calculate the subfactorial. private decimal Subfactorial(decimal N) { if (N == 0) return 1; if (N == 1) return 0; return (N - 1) * (Subfactorial(N - 1) + Subfactorial(N - 2)); }

Simple!

If you divide the total number of permutations N! by the number of derangements !N, you can calculate the fraction of the permutations that are valid derangements. The following graph shows the percentage of permutations that are derangements for N = 1 to 10.

The percentage very quickly converges on 36.787944 percent. That means if you're trying to randomly pick a derangement, the chances are pretty good you'll find one in only a few tries.

To use the example program, enter a value for N and click the Calculate button. The program calculates N!, !N, and the percentage !N / N! * 100 and displays them. If N ≤ 10, it also finds the derangements and displays up to 1,000 of them.

One final note. The doubly-recursive Subfactorial function is fairly inefficient. To calculate !N, it must calculate !(N - 1) and !(N - 2). But to calculate !(N - 1), it must calculate !(N - 2) and !(N - 3). Here !(N - 2) is being calculated twice.

As you continue the calculations, you end up making lots of calculations many times. The result is a huge tree of repeated calculations that makes this method for calculating !N very inefficient.

This is the same reason the recursive method for calculation the Fibonacci numbers is very inefficient. In this case, however, !N grows so quickly that the decimal data type cannot handle values large than !27 anyway, so the function is limited by that before its performance hurts it. (Maybe I'll post something about the Fibonacci numbers later.)

Enumerating Derangements

The example uses the following code to build a list of derangements.

// Assign the next person to position pos. void AssignPerson(List<List<int>> valid, int pos, int N, int[] assignments, bool[] is_assigned) { // If pos >= N, then we have a complete assigment. if (pos >= N) { // Save this assignment. List<int> result = new List<int>(); for (int i = 0; i < N; i++) result.Add(assignments[i]); valid.Add(result); } else { // Assign people to position pos. for (int per = 0; per < N; per++) { // See if person per has been assigned. // Only make the assigment if per != pos. if ((per != pos) && (!is_assigned[per])) { // Assign person per to position pos. assignments[pos] = per; is_assigned[per] = true; // Recursively try other assignments. AssignPerson(valid, pos + 1, N, assignments, is_assigned); // Unassign person per from position pos. is_assigned[per] = false; } } } }

The input parameter valid is a list that will hold the derangements. Each item in the list is also a list containing the people in a particular permutation.

The parameter pos tells the method which position in the derangement it should fill. For example, when pos is 10, the method is picking a person for the 10th spot in the permutation.

Parameter N gives the number of people. (You could get it from the lengths of the arrays, but this is easier.) The assignments array holds the indices of the people assigned so far in this derangement.

Finally, is_assigned is true for people who have been added to the current solution. For example, if person 7 has been assigned to position 5 in the solution, then assignments[5] is 7 and is_assigned[7] is true.

The method first compares pos to N. If pos >= N, then the method has assigned everyone to a position and the derangement is complete. In that case the code adds the current assignment to the valid list and returns.

If the assignment isn't complete, the code loops through the people. If the is_assigned array indicates that a person is not yet assigned and that person's index isn't the same as the index the method is assigning pos (because that assignment would be disallowed for this person), the program adds the person to the derangement at position pos. It then recursively calls itself to assign the rest of the derangement. When the recursive call returns, the code removes the person from that position and continues.

This method enumerates all of the possible derangements without building any permutations that are not valid derangements, so in that sense it's quite efficient. The number of derangements !N grows very quickly, however, so the program contains some code to prevent it from finding derangements for more than 10 people.

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