检查给定的 Matrix(m*n) 中是否有任何可以转置的矩阵

Question

我需要检查是否可以找到给定大小为 5*8 的矩阵的内部一个具有转置的矩阵，如果有多个，我必须找到最大的一个。

给定矩阵的示例

1 2 0 3 2 1 0 7
2 3 4 1 2 3 4 5
3 4 6 2 5 6 7 6
4 5 7 3 6 8 9 8
6 7 1 4 7 9 0 9

在这个矩阵中我们可以找到一个4x4的矩阵具有转置及其在主矩阵中最大的矩阵

#include <stdio.h>

#define M 4
#define column 5
#define row 8

int main()
{
    int matrixA[5][8];

printf("please enter a matrix to check if there is a transpose matrix\n");
    for (int i = 0; i < column; i++)
    {
        for (int j = 0; j < row; j++)
        {
            printf("please enter %d row and %d column: ", i + 1, j + 1);
            scanf("%d", &matrixA[i][j]);
        }
    }
transpose(matrixA, column, row);

}

void transpose(int A[][row], int c, int r)
{
    int matrixAT[M][M];
    

    for (int size = r; size > 0; size--)
    {
        for (int j = 0; j < c - size + 1; j++)
        {
            for (int b = 0; b <= r - size; b++)
            {
                printf("Checking Matrix at row: %d , column: %d ,size: %dx%d", j, b, size, size);
                for (int k = j, w = 0; k < size + j; k++, w++)
                {
                    for (int l = b, z = 0; l < size + b; l++, z++)
                    {
                        matrixAT[w][z] = A[k][l];
                    }
                    printf("/n");
                }
                if (IsSymmetric(matrixAT, size))
                    printf("Matrix found");
            }
        }
    }
}
int IsSymmetric(int mat[M][M], int size)
{
    int flag = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (mat[i][j] == mat[j][i]) flag++;
                

        }
    }
    return flag == size * size ? 1 : 0;
}

这是我的代码我不知道我做错了什么

Answer 1

你可以制作一个函数来检查矩阵是否可以转置和另一个函数，它从主矩阵中抽出一部分时间，你每次都移动它并用第一个函数检查它例子：第一个矩阵：m[1][1] 从零开始 1 2 2 3 2 矩阵 :m[2][2] 从一个开始 2 0 3 4 然后当你完成 2 维矩阵时，你转到 3 直至最后我希望你能理解我，抱歉我的英语不好

Answer 2

您的 IsSymmetric 很慢，因为它总是检查所有元素，为什么不停止在第一个不等式上呢？还一次又一次地将它复制到临时数组...

主要问题是您在调用 transpose(matrixA, column, row); 时没有检查每个位置和大小，只在循环外调用一次...

而且你的 main 没有 return 任何东西并且它被声明为 int ...

我会像这样从蛮力开始：

#define column 5
#define row 8
int IsSymmetric(int mat[column][row], int i0,int j0,int size) // check n*n sub matrix at i0,j0 no need to copy again and again to temp array
    {
    for (int i = 0; i < size; i++)
     for (int j = 0; j < size; j++)
      if (mat[i0+i][j0+j] != mat[i0+j][j0+i]) return 0;
    return 1;
    }
int min(int a,int b){ return (a<b)?a:b; } // not sure if min is present in your environment if is comment this line out
int main()
    {
    int matrixA[5][8];
    ...
    for (int i = 0; i < column; i++)
     for (int j = 0; j < row; j++)
      for (int n = 1; n <= min(column-i,row-j); n++)
       if (IsSymmetric(matrixA,i,j,n))
        {
        // here do what you want with the i,j,n*n sub matrix
        // like remember position and size for the biggest n
        }
    ...
    return 0; // return value as you declared int main
    }

希望我没有在此处输入任何错误，因为我只是根据您的原始代码将其写入答案编辑器。

正如您所见，它的 O(n^4) 复杂度（平均 O(n^3)）非常慢。但是对于你的小矩阵来说这不是问题。

如果您需要更快的速度，那么我们需要了解更多关于数据的信息...例如值的范围是多少？一些提示：

在正 IsSymmetric 上测试一个更大的单元格子矩阵而不再次测试前面的元素（递归增加对角线）。
使用直方图检测可能仅在对角线上出现的值（全局出现一次或局部出现奇数次）

在O(n^3)解决方案中使用增量对称性测试结果：

//---------------------------------------------------------------------------
#define column 5
#define row 8
//---------------------------------------------------------------------------
void submatrix_print(int mat[column][row], int i0,int j0,int n,int m)
    {
    int i,j;
    printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
    for (i=0;i<n;i++,printf("\r\n"))
     for (j=0;j<m;j++)
      printf("%1i ",mat[i0+i][j0+j]);
    }
//---------------------------------------------------------------------------
void submatrix_print_transposed(int mat[column][row], int i0,int j0,int n,int m)
    {
    int i,j;
    printf("%i*%i at %i,%i\r\n",n,m,i0,j0);
    for (i=0;i<m;i++,printf("\r\n"))
     for (j=0;j<n;j++)
      printf("%1i ",mat[i0+j][j0+i]);
    }
//---------------------------------------------------------------------------
int min(int a,int b){ return (a<b)?a:b; }
int submatrix_symmetric(int mat[column][row], int i0,int j0) // returns biggest symetric submatrix size >=1 found at i0,j0
    {
    int i,n,N;
    N=min(column-i0,row-j0);    // max size that still fits into matrix
    for (n=2;n<N;n++)           // test all sizes above 1
     for(i=0;i<n-1;i++)         // only test newly added cells to last sub matrix
      if (mat[i0+n-1][j0+i]!=mat[i0+i][j0+n-1])
       return n-1;              // first non match means last tested size i svalid
    return n;                   // no mismatches mean full size is valid
    }
//---------------------------------------------------------------------------
int main()
    {
    int mat[5][8]=
        {
        1,2,0,3,2,1,0,7,
        2,3,4,1,2,3,4,5,
        3,4,6,2,5,6,7,6,
        4,5,7,3,6,8,9,8,
        6,7,1,4,7,9,0,9,
        };
    submatrix_print(mat,0,0,5,8);
//  submatrix_print_transposed(mat,0,0,5,8);

    int i,j,n,i0=0,j0=0,n0=0;
    for(i=0;i<column;i++)
     for(j=0;j<row;j++)
        {
        n=submatrix_symmetric(mat,i,j);
        if (n0<n){ n0=n; i0=i; j0=j; }
        }
    submatrix_print(mat,i0,j0,n0,n0);
    return 0;
    }
//-------------------------------------------------------------------------

代码的结果是：

5*8 at 0,0 // input matrix
1 2 0 3 2 1 0 7 
2 3 4 1 2 3 4 5 
3 4 6 2 5 6 7 6 
4 5 7 3 6 8 9 8 
6 7 1 4 7 9 0 9 

4*4 at 1,3 // biggest symmetric sub matrix found
1 2 3 4 
2 5 6 7 
3 6 8 9 
4 7 9 0

检查给定的 Matrix(m*n) 中是否有任何可以转置的矩阵

Check whether a given Matrix(m*n) has any matrix inside of it that can be transposed

c

arrays

math

matrix

char