如何在Java或C++中生成给定二维矩阵的所有子矩阵？

Question

我正在使用这个循环结构，但它无法生成给定2D矩阵（具有n行和m列）的所有可能子矩阵。

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

例：给定矩阵3X3: [[1 2 3]，[4 5 6]，[7 8 9]] 那么它的子矩阵将是： 大小为1： [1]，[2]，[3]，[4]，[5]，[6]，[7]，[8]，[9] 大小为4： [[1,2]，[4,5]]，[[2,3]，[5,6]]，[[4,5]，[7,8]]和[[5,6]，[8,9]] 以此类推

- mohdanishh

---

请提供更多细节：输入是什么，期望的输出和实际输出分别是什么？ - K. Kirsz

子矩阵的大小是多少？ - Sanket Makani

@UnholySheep，Stack Overflow已经有了解决这个问题的方法，但它是用Python编写的，并使用了一些Java或C++中不可用的内置函数。 - mohdanishh

@fzd的任务是显示所有子矩阵，但我无法完成。如果您能提供算法或伪代码，那将非常有帮助。 - mohdanishh

在矩阵中找到每个可能子矩阵的和是否有高效的方法？ - Himanshuman

Answer 1

您需要添加几个循环以涵盖所有情况。PrintMatyrix()应该有2个嵌套循环来打印内容。

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

- Michaël Roy

Answer 2

如果我们有一个尺寸为M x N的矩阵，并且我们要查找的子矩阵的尺寸是K x L。如果有更优化的解决方案，请分享。

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("*****************");

                }
            }

- Frosina Andonovska

Answer 3

你不应该使用循环，而应该使用递归。

可以这样考虑，对于每一行或列，你要么选择它，要么舍弃它。因此，你可以先选择行，然后选择列，并根据所选的行和列构建子矩阵。

以下是一些代码：

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

- Jerry Chou

---

函数printSubMatrix()的行和列边界是什么？ - mohdanishh

@mohdanishh，printSubMatrix仅用于打印使用rowTaken和columnTaken构建的子矩阵。请查看更新后的伪代码。 - Jerry Chou

如果您能构建函数printSubMatrix()，那将非常有帮助，这将有助于我完全理解您的算法。谢谢。 - mohdanishh

@mohdanishh，请刷新并查看更新后的代码。 - Jerry Chou