Number of permutation with K inversions - GeeksforGeeks

Number of permutation with K inversions - GeeksforGeeks

Given an array, an inversion is defined as a pair a[i], a[j] such that a[i] > a[j] and i < j. We are given two numbers N and k, we need to tell how many permutation of first N number have exactly K inversion.

A Naïve way to solve this problem is noting down all permutation then checking count of inversion in them but iterating through permutation itself will take O(N!) time, which is too large.
We can solve this problem using dynamic programming approach. Below is recursive formula.

If N is 0, Count(0, K) = 0

If K is 0, Count(N, 0) = 1 (Only sorted array)

In general case, 
If we have N number and require K inversion, 
Count(N, K) = Count(N - 1, K) + 
              Count(N – 1, K - 1) + 
              Count(N – 1, K – 2) + 
              .... + 
              Count(N – 1, 0)

// Limit on N and K

const int M = 100

 

// 2D array memo for stopping solving same problem

// again

int memo[M][M];

 

// method recursively calculates permutation with

// K inversion

int numberOfPermWithKInversion(int N, int K)

{

    //  base cases

    if (N == 0)

        return 0;

    if (K == 0)

        return 1;

 

    //  if already solved then return result directly

    if (memo[N][K] != 0)

        return memo[N][K];

 

    // calling recursively all subproblem of

    // permutation size N - 1

    int sum = 0;

    for (int i = 0; i <= K; i++)

    {

        // Call recursively only if total inversion

        // to be made are less than size

        if (i <= N - 1)

            sum += numberOfPermWithKInversion(N-1, K-i);

    }

 

    //  store result into memo

    memo[N][K] = sum;

 

    return sum;

}

Read full article from Number of permutation with K inversions - GeeksforGeeks