Derangement Is the New Normal (Combinatorics)
No, not really, that would be an insane title but then that’s what this post is about. Actually, no, that’s not quite right. I recently read about a combinatorial problem of generating permutations such that no element is placed in its original position, and that’s what this post is about. Derangement is what such a permutation is called.
For example, let’s say in a peer reviewed course, an assignment is to be distributed to students then it makes sense that each student gets an assignment to review other than one’s own. Concretely, if there are three students named Napoleon, Snowball, and Squealer*, then a possible permutation would be that Napoleon review Snowball’s assignment, Snowball review Squealer’s, and Squealer review Napoleon’s.
*Disclaimer: Yes, these are the pigs from Animal Farm** by Orwell and apologies for my drawing.
**Disclaimer on the Disclaimer: The names do not reflect any aspect of the story.
A possible derangement of the above assignments for peer reviewing would be as follows:
But why am I writing about this? For myself mostly, as it helps to understand some concepts better when one writes about them.
Here, I will be discussing two aspects of derangement, the number of ways such arrangements can be made i.e. counting derangements, and how to generate such arrangements.
Counting Derangements
The total number of permutations possible for our 3 students reviewing 3 papers are 6 as depicted below.
Only two of them are derangements because only two such arrangements result in a permutation where no student is reviewing it’s own assignment.
One way to find out how many derangements exist for any given number of items/elements is to use Inclusion-Exclusion Principle.
Inclusion-Exclusion Principle
Using this principle, we can count the number of derangements as follows:
Derangement count = All permutations -|Napoleon reviewing its own ⋃ Squealer reviewing its own ⋃ Snowball reviewing its own|
All permutations are n!, so we can rewrite as:
Derangement count = 3! - |Napoleon reviewing its own ⋃ Squealer reviewing its own ⋃ Snowball reviewing its own|
*⋃ means Union
As you can see in Figure-3 the number of arrangements such that each student is reviewing its own assignment is 2 for each of the three students. However, the first arrangement is counted multiple times while it should have been counted only once. So to count the union of all permutations that contains a student reviewing it’s own paper, we will adjust for the over counted.
|Napoleon reviewing its own U Squealer reviewing its own U Snowball reviewing its own | = |Napoleon reviewing its own| + |Squealer reviewing its own|+ |Snowball reviewing its own| - |Napoleon reviewing its own ⋂ Squealer reviewing its own|- |Napoleon reviewing its own ⋂ Snowball reviewing its own|- |Squealer reviewing its own ⋂ Snowball reviewing its own| + |Squealer reviewing its own ⋂ Snowball reviewing its own ⋂ Napoleon reviewing its own|
*⋂ means intersection
Even I cannot read what’s going on up there, so I’ll assign letters instead. Consider as follows:
A => Napoleon reviewing its own
B => Squealer reviewing its own
C => Snowball reviewing its own
|A ⋃ B ⋃ C| = |A| + |B| + |C| - |A ⋂ B| - |A ⋂ C| - |B ⋂ C| + |A ⋂ B ⋂ C|
|A ⋃ B ⋃ C| = 2 + 2 + 2 - 1 -1 -1 + 1
|A ⋃ B ⋃ C| = 4
Now we can plug this value to get the derangement count.
Derangement count = 3! - |Napoleon reviewing its own U Squealer reviewing its own U Snowball reviewing its own|
Derangement count = 6-4
Derangement count = 2
This is all good but there is another intuitive approach available to us that counts the number of derangements using recursion.
Count Derangements Using Recursion
I must tell you that it took me a while to understand the intuitive approach. Fortunately, a book that I mostly used as a monitor stand delivered me out of my misery and got me past my mental block.
If there was only one student, let’s say Snowball, then how many ways can he review an assignment not of its own? That would be 0 ways. There is only one assignment written by Snowball, so there is no peer to review his assignment and no other assignment for him to review.
What if there were only two students, let’s say Snowball and Squealer? Then there will be only one possible derangement such that no student review it’s own assignment. Snowball reviews Squealer’s, and Squealer reviews Snowball’s.
So, we’ve established a base case for our recursion. If there are two students, then there is only one derangement possible and if there is only one student then there is no derangement possible.
For any number N higher than 2, you can think of it this way: One of the student takes an assignment to review from one of the other N-1 students. Let’s say Napoleon takes the assignment done by Squealer, then we can be assured that at least one of the students (Napoleon) is reviewing assignment other than its own. Now there are N-1 students left to be deranged.
Let’s add one more student, Old Major, to make it more interesting.
Napoleon gets the assignment done by Squealer:
But what about Napoleon’s assignment? Should it be reviewed by Squealer? Yeah, but it’s not necessary, right? Maybe Snowball can review Napoleon’s paper, Squealer review Old Major’s and Old Major review Napoleon’s paper.
So, you see there are two ways this can play out, 1: Napoleon takes Squealer’s paper and Squealer takes Napoleon’s, 2: Napoleon takes Squealer’s paper, and someone other than Squealer takes Napoleon’s paper.
In case 1 when two students exchange their papers, we are left with N-2 students in need of derangement.
In case 2, we only know that Napoleon has Squealer’s assignment and we want Napoleon’s assignment get reviewed by someone other than Squealer. We can do so by first giving Squealer, Napoleon’s assignment and getting a derangement between Snowball, Old Major, and Squealer, that way Napoleon’s assignment will not be reviewed by Squealer.
Now, we made an arbitrary decision to select Napoleon and Squealer but it could have been any of the other students. So this mean any of the N-1 students could have taken the place of Napoleon, therefore, this process needs to be repeated for the rest of the N-1.
Considering the above two cases, our recurrence relation can be stated as follows:
To code this, we don’t necessarily need to use recursion, as we are only ever needing to know two values D(N-2) and D(N-1) that we can keep track of inside a for loop but this is an exercise for getting practice in recursion, so I’ll use it anyways.
I used lru_cache to optimize for overlapping subproblems. This way, I don’t need to compute again the values of n already worked out. Since I only care about the last two values, i.e. n-2 and n-1, I set the cache size to be 2. If I were to reuse it often for different values of n, then it would make sense to cache more results than just the last two.
Following shows the derangement counts reported by the above algorithm:
You could also write the program to compute this number starting from 1 and going up to N without using recursion.
Generating Derangement
Now that the counting is out of the way, let’s have some fun generating derangement for our students.
I’m going to change something here though, instead of finding derangements on specific lists, I’ll find derangements on an array of a specific size, making it generic. That way, when I get all the derangements, I will use it as a template to generate derangement of the original list.
For example, I will treat the list [‘Snowball’, ‘Napoleon’, ‘Squealer’, ‘Old Major’] as [0, 1, 2, 3].
Each index or position means the student, while the value it is holding means the assignment of the student.
Snowball is represented by index 0
Napoleon is represented by index 1
Squealer is represented by index 2
Old Major is represented by index 3
Now, if we get a derangement represented by this array: [2, 3, 1, 0], it means that Snowball represented by 0th index is reviewing Squealer’s assignment because 2 represents Squealer. Consecutively, this derangement would translate into: [‘Squealer’, ‘Old Major’, ‘Napoleon’, ‘Snowball’].
The algorithm below swaps the starter element with the last element of the list and recursively calls itself by incrementing the starter element index and thereby reducing the size of the problem by 1.
`find_derangements_of_size` is a wrapper that accepts an integer indicating the number of elements for which the derangements are to be generated. In our case, that will be 4. Line 20 just create this list i.e. [0, 1, 2, 3]
`find_derangement_helper` is then called with initial value of k as 0. So, the loop on line 11 will consider all elements from index 3 (length of the list minus 1) to index 0. The index k is fixed at each level of the tree and its value is swapped with the element at index i which is the loop variable (line 15–16), provided if such a swap does not end up placing the element in its original position (line 12–13). Once the call returns, the original value of the k’th index is restored in line 17 and next i’th element is considered. When ‘k’ reaches the size of the elements list, a derangement is found and copied to d_list, line 7–9.
Line 28–29 uses the derangements on the generic list to create derangements on the original list.
Line 33 to 35 shows usage of the above class. The output of running the program is as follows:
Last Words
For lack of a better title. I’m not summarizing anything here. Just want to conclude. I may add few more things to the article later such as the recursion tree created by the 2nd code snippet. Please let me know if you find any mistakes.
References
- Where I first learnt about derangements:
- The book I used as monitor stand that helped me understand one of the concept in the recurrence relation:
Applied Combinatorics by Fred Roberts (Author), Barry Tesman (Author)
- Guide to Competitive Programming by Antti Laaksonen https://link.springer.com/book/10.1007/978-3-319-72547-5
- https://rosettacode.org/wiki/Permutations/Derangements
