Count permutation such that sequence is non decreasing | C ++ implementation of the approach ; To store the factorials ; Function to update fact [ ] array such that fact [ i ] = i ! ; 0 ! = 1 ; i ! = i * ( i - 1 ) ! ; Function to return the count of possible permutations ; To store the result ; Sort the array ; Initial size of the block ; Increase the size of block ; Update the result for the previous block ; Reset the size to 1 ; Update the result for the last block ; Driver code ; Pre - calculating factorials
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  20 NEW_LINE int fact [ N ] ; void pre ( ) { fact [ 0 ] = 1 ; for ( int i = 1 ; i < N ; i ++ ) { fact [ i ] = i * fact [ i - 1 ] ; } } int CountPermutation ( int a [ ] , int n ) { int ways = 1 ; sort ( a , a + n ) ; int size = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( a [ i ] == a [ i - 1 ] ) { size ++ ; } else { ways *= fact [ size ] ; size = 1 ; } } ways *= fact [ size ] ; return ways ; } int main ( ) { int a [ ] = { 1 , 2 , 4 , 4 , 2 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; pre ( ) ; cout << CountPermutation ( a , n ) ; return 0 ; }