搜索部分对称的算法

Question

我正在尝试以百分比计算具体矩阵的对称性。

"traditional" 计算对称性的方法是，我将大小为 N×N 的任意方阵 M 作为输入，并且算法的输出必须为真（=对称），如果 M[i,j ] = M[j,i] 对于所有 j≠i，否则为假。

如何适当处理计算百分比？所以不只是说对称或不对称？也许计算 j≠i 的次数并将其除以 (i,j) 的总量？

所以f.e。如果我有以下矩阵：

    1 1 1        1 1 1 
A = 2 2 2    B = 2 2 2
    1 1 2        3 4 5

那么我需要知道 A 比 B 是 "more symmetric"，即使两者都是非对称。

Answer 1

您应该首先定义每个单元格的对称距离度量。如果对称单元格相同，则该值应为零，否则应为其他数字。

例如：

s(i,j):= (m(i,j)==m(j,i) ? 0:1) // returns 0/1 if the symmetric cell is/isn't the same

或

s(i,j):= |m(i,j)-m(j,i)| // returns the absolute difference between the two cells

然后将所有单元格的距离相加：

int SymmetricDistance(matrix){
  for (int i=0; i<matrix.Width; i++)
    for (int j=i; j<matrix.Width; j++) // check if th matrix is square first
      dist = dist + s(i,j);
  return dist;
}

现在你可以说矩阵 A 比矩阵 B "more symmetric" 当且仅当

SymmetricDistance(A) < SymmetricDistance(B)

Answer 2

我总体上同意@Sten Petrov 的回答。但是，如果您正在寻找特定的 百分比 对称性：

首先，求NxN矩阵中对称元素对的总数。

您可以通过沿对角线拆分矩阵并计算元素的数量来找到它。由于将 1 添加到 N 会使总对数增加 N，因此找到total pairs 是对从 1 到 N 的数字求和。但是，不要循环只使用求和公式：

Total Possible = N * (N + 1) / 2

矩阵完全对称当且仅当所有对都是对称的。因此，对称百分比可以定义为对称对占所有可能对的分数。

Symmetry = Symmetric Pairs / Total Pairs

伪代码：

int matchingPairs= 0;
int N = matrix.Width;
int possiblePairs = N * (N + 1 ) / 2;

for(int i = 0; i < N; ++i){
    for(int j = 0; j <= i; ++j){
        matchingPairs += (matrix[i][j] == matrix[j][i]) ? 1 : 0;
    }
}

float percentSymmetric = matchingPairs / possiblePairs ;

搜索部分对称的算法

Algorithm for partial symmetry searched

algorithm

symmetric

matrix