Number of permutation with K inversions | C ++ program to find number of permutation with K inversion using Memoization ; Limit on N and K ; 2D array memo for stopping solving same problem again ; method recursively calculates permutation with K inversion ; base cases ; if already solved then return result directly ; calling recursively all subproblem of permutation size N - 1 ; Call recursively only if total inversion to be made are less than size ; store result into memo ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int M = 100 ; int memo [ M ] [ M ] ; int numberOfPermWithKInversion ( int N , int K ) { if ( N == 0 ) return 0 ; if ( K == 0 ) return 1 ; if ( memo [ N ] [ K ] != 0 ) return memo [ N ] [ K ] ; int sum = 0 ; for ( int i = 0 ; i <= K ; i ++ ) { if ( i <= N - 1 ) sum += numberOfPermWithKInversion ( N - 1 , K - i ) ; } memo [ N ] [ K ] = sum ; return sum ; } int main ( ) { int N = 4 ; int K = 2 ; cout << numberOfPermWithKInversion ( N , K ) ; return 0 ; }