Number of permutation with K inversions | 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
M = 100 NEW_LINE memo = [ [ 0 for i in range ( M ) ] for j in range ( M ) ] NEW_LINE def numberOfPermWithKInversion ( N , K ) : NEW_LINE INDENT if ( N == 0 ) : return 0 NEW_LINE if ( K == 0 ) : return 1 NEW_LINE if ( memo [ N ] [ K ] != 0 ) : NEW_LINE INDENT return memo [ N ] [ K ] NEW_LINE DEDENT sum = 0 NEW_LINE for i in range ( K + 1 ) : NEW_LINE INDENT if ( i <= N - 1 ) : NEW_LINE INDENT sum += numberOfPermWithKInversion ( N - 1 , K - i ) NEW_LINE DEDENT DEDENT memo [ N ] [ K ] = sum NEW_LINE return sum NEW_LINE DEDENT N = 4 ; K = 2 NEW_LINE print ( numberOfPermWithKInversion ( N , K ) ) NEW_LINE