恒等行列である最大サブマトリクス

Question

恒等行列である最大のサブ行列を見つけようとしています。私は可能なすべての部分行列をどのように走らせるべきか分かりません。すべての部分行列をループ内の任意の助けをいただければ幸いです

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の初心者であることを覚えておいてください。

Answer 1

このようなことを試すことができます。そのmartrixがアイデンティティか

ノートであれば、このプログラム

が真のサブ行列 -Returnsを-Finds：これはn×nの行列のために動作しますが、簡単にn×mの行列で動作するように微調整することができます。

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部分行列をチェックすることができます。