Count Derangements (Permutation such that no element appears in its original position)
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.
Examples :
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}
Input: n = 4
Output: 9
For four elements say {0, 1, 2, 3}, there are 9
possible derangements {1, 0, 3, 2} {1, 2, 3, 0}
{1, 3, 0, 2}, {2, 3, 0, 1}, {2, 0, 3, 1}, {2, 3,
1, 0}, {3, 0, 1, 2}, {3, 2, 0, 1} and {3, 2, 1, 0}
So the java code for the above program is:
import java.util.Arrays;
public class Main {
static int countDer(int n)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (countDer(n - 1) + countDer(n - 2));
}
public static void main (String[] args)
{
int n = 4;
System.out.println( "Count of Derangements is "
+countDer(n));
}
}
Time Complexity : O(2^n)
Dynamic programming approach
import java.util.Arrays;
public class Main {
static int countDer(int n,int[] dp)
{
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
if(dp[n] != -1)
return dp[n];
dp[n] = (n - 1) * (countDer(n - 1,dp) + countDer(n - 2,dp));
return dp[n];
}
public static void main (String[] args)
{
int n = 5;
int[] dp = new int[n+1];
Arrays.fill(dp,-1);
System.out.println( "Count of Derangements is " +countDer(n,dp));
}
}
Time Complexity : O(n)
Space Complexity : O(n)
0 Comments