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