## Friday, November 11, 2016

### 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;`
`}`