Count Derangements ( Permutation such that no element appears in its original position ) | C ++ implementation of the above approach ; Function to count derangements ; base case ; Variable for just storing previous values ; using above recursive formula ; Return result for n ; Driver Code
#include <iostream> NEW_LINE using namespace std ; int countDer ( int n ) { if ( n == 1 or n == 2 ) { return n - 1 ; } int a = 0 ; int b = 1 ; for ( int i = 3 ; i <= n ; ++ i ) { int cur = ( i - 1 ) * ( a + b ) ; a = b ; b = cur ; } return b ; } int main ( ) { cout << " Count ▁ of ▁ Dearrangements ▁ is ▁ " << countDer ( 4 ) ; return 0 ; }