c++ - 检查网格/真值表的对称性

Question

t t f f f f t t
t t f f f f t t
f f t t t t f f
f f t t t t f f
t t f f f f t t
t t f f f f t t
f f t t t t f f
f f t t t t f f

是否可以使用 8 输入真值表（例如 OR、AND、XOR 等）确定上述 8x8 的对称性？

Answer 1

所以，我在评论中所说的是反复检查某些对并对它们进行“NOT XOR”。

对的想法是，如果一行是对称的，则某些对必须相等。注意到我们将索引数组归零，我们在每一行中都有索引 0 和 7、1 和 6、2 和 5、3 和 4。为了使行对称，所有 4 个必须是配对。总之，要使表对称，需要检查 32 对（每行 4 对，超过 8 行）。

NOT XOR 的诀窍是，由于 XOR 在两者不同时返回 true，因此如果两者相同，则该语句的否定返回 true。

所以，如果你想只使用布尔运算来完成整个检查，你会得到每一对，（现在称之为 (a,b) ）并执行 (NOT(a XOR b)) （!(a^b)在代码中），然后是所有 32 项检查的结果。

当然，如果我实际上是在代码中执行此操作，我宁愿定期检查是否相等。

Answer 2

假设你的意思和我一样的对称性，并且你有类似 abool[][]或 an的输入std::vector<std::vector<bool> >（或者char代替bool，只要有效，它并不重要==），你只需迭代一半矩阵和与另一半比较，是这样的：

bool symmetric = true;
for (unsigned int i = 1; symmetric && i <= n; ++i) {
  for (unsigned int j = i+1; symmetric && j <= n; ++j) {
    symmetric = (M[i][j] == M[j][i]);
  }
}

请注意，您不需要检查对角线，这就是上面代码中i从 1 和jat开始的原因。i+1

（我倾向于写比某些人喜欢的更多的括号和大括号。我只是碰巧更喜欢这样编写的代码。）

---

编辑：

当然，您可以有一个 64 输入表来告诉您哪些输入是对称的。通过一些压缩，您可以将该表存储在 2097152 TB 的内存中。我猜在您完成加载此表以进行查找之前，循环代码可以经常运行。相反，您当然可以将平行于反对角线的六条非平凡线输入相应的真值表，因为如果它们是对称的，则整个矩阵是对称的。这些表（用于 2、3、4、5、6、7 和 8 个输入）很容易放入几百个字节。

但无论如何，您对对称性的解释似乎与我的不同。如果您对每一行和/或每一列是否对称感兴趣，那么显然，您可以为此使用真值表。遍历它们需要 256 位，所以如果你的空间真的很短，你可以将它们压缩成 8 位，但是当你在它上面花费 256 字节时，查找可能会更快。