作为单位矩阵的最大子矩阵

debugcn 发表于 Dev

用户8256267

我试图找到作为单位矩阵的最大子矩阵。我不知道如何遍历所有可能的子矩阵。然而，我设法想出了一个函数来确定矩阵是否是身份：

function isIdentityMatrix(matrix) {

  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix.length; j++) {
      if (matrix[i][j] !== 1 && i === j || matrix[i][j] && i !== j) {
        return false;
      }
    }
  }
  return true;
}

任何帮助遍历所有子矩阵的帮助将不胜感激。请记住，我是 javascript 的新手。

维多维斯特罗姆

你可以尝试这样的事情。这个程序

- 找到一个子矩阵 - 如果该矩阵是身份，则返回真

注意：这仅适用于 nxn 矩阵，但可以轻松调整以使用 nxm 矩阵。

   let arr=[

[1,1,1,0,0],
[0,1,1,0,0],
[0,0,1,0,0],
[1,0,1,1,0],
[0,0,0,1,1]

];

let finalValue=0;
 let n=arr.length;

 let N=2;//size of submatrices

 function subMatrix(k,n,N,arr)
{


    let max_k_x=n-N+1;// per row max value of k
    let row=Math.floor(k/max_k_x);
    let col=k%max_k_x;


    /* 
      k=6,n=4,N=2
      max_k=(4-2+1)*(4-2+1)=9
      max_k_x=3
      row=2(starting from zero)
      col=0
    */

let matrix=new Array();

for(let i=row;i<row+N;i++){
  for(let j=col;j<col+N;j++){

    matrix.push(arr[i][j]);

  }
}

return matrix;
}

 function doSomethingWithMatrix(matrix,N){

for(let i=0;i<matrix.length;i++){

        if((matrix[i] && (i%(N+1)!==0))||(matrix[i]!==1 && (i%(N+1))===0)){

     return false;


    }

    }





 return true;
}

 for(let k=0;k<(n-N+1)*(n-N+1);k++){//k can vary from 0 to (((n-N+1)^2)-1)

     let matrix=new Array();
  matrix=subMatrix(k,n,N,arr);
 // console.log(doSomethingWithMatrix(matrix,N));
   //  console.log("   ");
if(doSomethingWithMatrix(matrix,N)){

        finalValue=N;
         N++;
         k=0;
         if(N===n){
             N--;
             break;
         }

     }
     if(k===(n-N+1)*(n-N+1)-1){
         N++;
     }
     matrix=[];

}
console.log("final N: "+finalValue);

您可以更改循环内的值 N 以检查 NxN 子矩阵。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。