I would like to explain the concept of derangement of a permutation.

Definition: Derangement of a permutation is another ordering where each and every element of the permutation is not in its original position.

Examples: A derangement of 1 2 3 can be 3 1 2, but 3 2 1 is not a derangement of 1 2 3 because 2 is still in its correct position.

Sometimes for an array, a derangement is not possible. Let us take an example.

Consider the array of numbers 1 2 1. Try writing the remaining permutations of this array, at least 1 element will retain its position.

Statement: If an element occurs more than 'half the size' number of times in an array then the derangement of that array is not possible.

Proof: Consider, an array of n elements. If there exists an element with a frequency that is greater than n / 2(take it as real division). Then the given array cannot be deranged because if we pick that particular element and try filling the remaining numbers into its original position, we will run out of numbers. For example, in the case of 1, 2, 2, 2, 3 In order for 2 to not be in its original set of positions, we need 1 and 3, which are the remaining distinct elements in the array, to fill in for 2. But there are 3 positions and only 2 numbers to occupy, hence every position will not be occupied, hence no derangement is possible. That concludes our proof.

When a derangement is possible, how do we construct it? Consider the case when elements are sorted. If we calculate the maximum frequency that a number has in an array, we can rotate the array by that amount and get the derangement of the given sorted array.

How is that possible?

Consider the n elements of a sorted array, a1, a2, ....., an. If we rotate the array by the maximum frequency, we are sure that the elements with the maximum frequency are not going to retain their original position as the series of similar numbers will be shifted ahead. For example, if we have, 1, 1, 2, 2, maximum frequency here is 2 and rotating by 2 yields 2, 2, 1, 1. In the forward direction, the ones are all ahead of the last one in the original permutation. So, in the forward direction, the array has kind of shifted right. No element will retain its position. You can try rotating 1, 1, 2, 2, 2, 3 by 3 to get a better feel or try out as many examples you want. As long as derangement is possible, and you rotate the array by maximum frequency, the new permutation of that sorted array is deranged.

Now how does this help in deranging an unsorted array? Simple, when you sort the array, keep the positions of each occurrence of the number with it. For example, for the array 1, 1, 6, 7, 8, 9, 1, 2, 2 the sorting would be (1, 1), (1, 2), (1, 7), (2, 8), (2, 9), (6, 3), (7, 4), (8, 5), (9, 6). Now when you rotate the sorted array by the maximum frequency, you will get the derangement of the sorted array, not of the actual one. So, keep an auxiliary array of the same size and go through the sorted array that stored the indices, sequentially from beginning and fill that index of the auxiliary array with the value of the rotated array that is equal to that retained index alongside the value(in the sorted array that is not rotated, look at the example). In a way, you are using the derangement of the sorted array to fill in the position of the numbers in the unsorted array. Let us consider an example. The array is 2, 1, 1, 2, 1, 3, 4, 5. If we sort the array and retain the indices, we have (1, 2), (1, 3), (1, 5), (2, 1), (2, 4), (3, 6), (4, 7), (5, 8). Now since the maximum frequency is 3(1 occurs thrice), we rotate this sorted array by 3, based on the first element. We now get, 3, 4, 5, 1, 1, 1, 2, 2.

3 goes to position 2 as in the corresponding array, the element is (1, 2)

4 goes to position 3 as in the corresponding array, the element is (1, 3)

5 goes to position 5 as in the corresponding array, the element is (1, 5)

1 goes to position 1 as in the corresponding array, the element is (2, 1) and, so on.

We get the following output, 1, 3, 4, 1, 5, 1, 2, 2 which is a derangement. If you observe carefully, the sorted version is just being modified, if a number x comes in position of y in case of sorted array, it just replaces y in its position in case of an unsorted array.

I would like to acknowledge this problem https://www.codechef.com/problems/MARCAPS for motivating me to write a blog on the topic. Hope the idea was clear enough and please point out errors, I will be happy to correct them. This is my first educational blog and I would like to contribute more if I find cool concepts like this in future.