CODEWITHSUNDEEP
javac++algorithm
mohdanishh
mohdanishh

Reputation: 61

How can we generate all submatrix of a given 2D matrix in java or C++?

I am using this loop structure but it fails to generate all the submatrix that are possible for any given 2D matrix with n rows and m columns.

  for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            System.out.println("sub-MATRIX:");
            for(k=i;k<n;k++)
            {
                for(p=j;p<m;p++)
                {
                   System.out.print(arr[k][p]+" ");
                }
                System.out.println();
            }
        }
    }

Ex: Given matrix 3X3 : [[1 2 3],[4 5 6],[7 8 9]] Then its submatrix will be: for size 1: [1],[2],[3],[4],[5],[6],[7],[8],[9] for size 4: [[1,2],[4,5]],[[2,3],[5,6]],[[4,5],[7,8]] and [[5,6],[8,9]] and so on

Upvotes: 4

Views: 9119

Answers (3)

Frosina Andonovska
Frosina Andonovska

Reputation: 21

If we have a matrix with dimensions M x N, and the sub matrix we are looking for is with K x L dimensions. If there is more optimized solution, please share.

for (int i = 0; i < m-k+1; i++) {   
                for (int j = 0; j < n-l+1; j++) {
                    for (int p = 0; p < k; p++) {
                        for(int q = 0; q < l; q++) {
                            System.out.print(arr[i+p][j+q] + " ");
                        }
                        System.out.println();
                    }
                    System.out.println("*****************");

                }
            }

Upvotes: 2

Jerry Chou
Jerry Chou

Reputation: 302

You should not loops, you should use some recursions.

Think about this way, for each row or column, you either take it or throw away it. So you can select rows first and then columns and based on the rows and columns selected you construct the submatrix.

Some code,

bool rowTaken[N], columnTaken[M];
void constructSubMatrixRow(int i)
{
    if (i >= N) constructSubMatrixCol(0);
    rowTaken[i] = true;
    constructSubMatrix(i+1);
    rowTaken[i] = false;
    constructSubMatrix(i+1);
}

void constructSubMatrixCol(int i)
{
    if (i >= M) printSubMatrix();
    columnTaken[i] = true;
    constructSubMatrixCol(i+1);
    columnTaken[i] = false;
    constructSubMatrixCol(i+1);
}

void printSubMatrix()
{
    for (unsigned i = 0; i < N; i++)
        if (rowTaken[i]){
            for (unsigned j = 0; j < M; j++)
               if (columnTaken[j])
                  print matrix[i][j]
        }
}

Upvotes: 0

Micha&#235;l Roy
Micha&#235;l Roy

Reputation: 6481

You are missing a couple more loops to cover all cases. PrintMatyrix() should have 2 nested loops for printing contents. 

  for (i = 1; i < n; ++i)
  {
    for (j = 1; j < m; ++j)
    {
      // we are at each sub matrix of size(i,j)
      for (k = 0; k <= (n - i); ++k)
      {
        for (p = 0; p <= (m - j); ++p)
        {
           // we are at submatrix of size(i,j) starting at (k,p)
           // assuming PrintMatrix(Matrix&, int rows, int cols, int r0, int c0);   
           PrintMatrix(arr, i, j, k, p);
        }
      }
    }
  }

Upvotes: 3

Related Questions