3

I have been given the number N. I have to find all the permutations of numbers 1..N such that the total number of inversions in the array is K.

For example: (all the following permutations have exactly 2 inversions) 
N=4 , K=2
(1,4,2,3) , (1,3,4,2) , (2,1,4,3) , (3,1,2,4) and (2,3,1,4).

My Approach:
Dynamic Programming: let dp[i][j] hold number of ways such that position i is responsible for j number of inversion.

dp[n][0]=1
 for(int i=n-1;i>=1;i--){

      int x = Math.min(k,n-i); // Maximum Number of inversion i position can do

      for(int j=0;j<=x;j++){

          for(int v=0;v<=j;v++){
                dp[i][j]+=dp[i+1][v];
            }

      }

But my approach give me individual position inversions, how can I get the total ways?

A. Sarid
  • 3,916
  • 2
  • 31
  • 56
user6250837
  • 458
  • 2
  • 21
  • 1
    Possible duplicate of [Number of n-element permutations with exactly k inversions](http://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions) – A. Sarid Sep 11 '16 at 10:51
  • @A.Sarid still can you improve my current implementation what i am missing – user6250837 Sep 11 '16 at 12:35

1 Answers1

0

Since for any permutation of 1,2...N-1, we can insert N, at position j, adding a total of N-j inversions, the total number of permutations of 1,2...N with k inversions may be calculated by

T(N,k) = T(N-1,k) + T(N-1,k-1) + T(N-1,k-2) ... + T(N-1,0)

JavaScript example:

function f(N,K){
  var M = [[1]];

  for (var n=1; n<=N; n++){
    M[n] = new Array((n-1)*n/2 + 1).fill(0);
    
    for (var k=0; k<=(n-1)*n/2; k++){
      for (var j=Math.min(k,(n-2)*(n-1)/2); j>= Math.max(0,k-n+1); j--){
        M[n][k] += M[n-1][j];
      }
    }
  }
  
  return M;
}

var res = f(5,10);

for (var i=0; i< res.length; i++){
  console.log(JSON.stringify(res[i]));
}
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • i have also done the same things `dp[i][j]+=dp[i+1][v]`; but when N=3,K=3 it gives me 0 – user6250837 Sep 12 '16 at 02:14
  • Maximum # of inversions for N = 2 is 1, no? So for T=3, the only place we can add it to T(2,1) to get 3 inversions would be in position 0, I think. Something like: `T(2,0) = {(1,2)}; T(2,1) = {(2,1)}; T(3,3) = {(3,2,1)}` – גלעד ברקן Sep 12 '16 at 10:36