algorithm - 求 K 次反转的排列总数

Question

我得到了号码 N。我必须找到数字 1..N 的所有排列，使得数组中的反转总数为 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).

我的方法:
动态规划:让 dp[i][j] 保存方式数，使得位置 i 负责 j 反转数。

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];
            }

      } 

但是我的方法给了我个别的位置反转，我怎样才能得到总的方式？

Answer 1

因为对于 1,2...N-1 的任何排列，我们可以在位置 j 插入 N，添加一个total of N-j inversions, 1,2...N with k inversions 的排列总数可以计算为

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

JavaScript 示例:

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]));
}