Count Derangements (Permutation such that no element appears in its original position) - GeeksforGeeks
A Derangement is a permutation of n elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Given a number n, find total number of Derangements of a set of n elements.
Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
Extended:
http://rosettacode.org/wiki/Permutations/Derangements#Java
http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html
Read full article from Count Derangements (Permutation such that no element appears in its original position) - GeeksforGeeks
A Derangement is a permutation of n elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Given a number n, find total number of Derangements of a set of n elements.
Input: n = 2 Output: 1 For two elements say {0, 1}, there is only one possible derangement {1, 0} Input: n = 3 Output: 2 For three elements say {0, 1, 2}, there are two possible derangements {2, 0, 1} and {1, 2, 0}
Let countDer(n) be count of derangements for n elements. Below is recursive relation for it.
countDer(n) = (n-1)*[countDer(n-1) + countDer(n-2)]
How does above recursive relation work?
There are n – 1 ways for element 0 (this explains multiplication with n-1).
There are n – 1 ways for element 0 (this explains multiplication with n-1).
Let 0 be placed at index i. There are now two possibilities, depending on whether or not element i is placed at 0 in return.
- i is placed at 0: This case is equivalent to solving the problem for n-2 elements as two elements have just swapped their positions.
- i is not placed at 0: This case is equivalent to solving the problem for n-1 elements as now there are n-1 elements, n-1 positions and every element has n-2 choices
int
countDer(
int
n)
{
// Create an array to store counts for subproblems
int
der[n + 1];
// Base cases
der[0] = 1;
der[1] = 0;
der[2] = 1;
// Fill der[0..n] in bottom up manner using above
// recursive formula
for
(
int
i=3; i<=n; ++i)
der[i] = (i-1)*(der[i-1] + der[i-2]);
// Return result for n
return
der[n];
}
int
countDer(
int
n)
{
// Base cases
if
(n == 1)
return
0;
if
(n == 0)
return
1;
if
(n == 2)
return
1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return
(n-1)*(countDer(n-1) + countDer(n-2));
}
Extended:
http://rosettacode.org/wiki/Permutations/Derangements#Java
http://math.illinoisstate.edu/day/courses/old/305/contentderangements.html
Suppose we want to determine the number of derangements of the n integers 1,2,...,n for n bigger than 2. Let us focus on k and move it into the first position. We thus have started a derangement, for 1 is not in its natural position. Where could 1 be placed? There are two cases we could consider: either 1 is in position k or 1 is not in position k.
If 1 is in position k, here's what we know: The integers 1 and k have simply traded positions.
Indicated by the question marks, there are (n-2) integers yet to derange. This can be done in D(n-2) ways.
If 1 is not in position k, we don't know as much. Note that we have shown 1 as a prohibited value twice. This is required for this case, because we cannot have 1 appear in the first position (its natural position) nor can 1 appear in position k.
Indicated by the question marks, there are now (n-1) integers yet to derange. This can be done in D(n-1) ways.
Putting this together, we have D(n-1) + D(n-2) possible derangements when k is in the first position. How many different integers could we put in position 1 and carry out this process? All the integers except 1. that is, (n-1) different integers.
This yields the recursive formula D(n) = (n-1)[D(n-1) + D(n-2)]. As long as we know D(1) = 0 and D(2) = 1, we can generate subsequent values for D(n).
intderangements_number( | int | n | ) |
A derangement of n objects is a permutation with no fixed points. If we symbolize the permutation by , then for a derangment, is never equal to .
The number of derangements of n objects is given by the following formula
Based on the inclusion/exclusion law we are allowed to write
where is the ceiling function.