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