Check the symmetry of a grid/truth table

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

Is it possible to determine the symmetry of the above 8x8 using 8-input truth tables e.g. OR, AND, XOR, etc?

Answer 1

Assuming you mean symmetry the same way I do and that you have the input in something like a bool[][] or an std::vector<std::vector<bool> > (or char instead of bool, it doesn't really matter as long as == works), you'd simply iterate over one half of the matrix and compare with the other half, something like this:

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

Note that you don't need to check the diagonal, which is why i starts at 1 and j at i+1 in the code above.

(I tend to write more parentheses and braces than some people like. I just happen to prefer code written that way.)

---

EDIT:

You can have a 64-input table that tells you which inputs are symmetric, sure. With a bit of compression, you could store that table in 2097152 TB of memory. I guess the looping code can run pretty often before you are finished loading this table for lookup. Instead, you could of course enter the six non-trivial lines parallel to the antidiagonal into corresponding truth tables, since if they are symmetric, the whole matrix is. Those tables (for 2, 3, 4, 5, 6, 7, and 8 inputs) would easily fit into a few hundred bytes.

But it seems your interpretation of symmetry is different from mine, anyway. If you are interested in whether each row and/or each column is symmetric, then, obviously, you can use truth tables for that. Stroing them takes 256 bits, so if you are really short on space, you could squeeze them into 8 bits, but lookup is probably faster when you spend 256 bytes on it.

Answer 2

So, what I said in the comment is to repeatedly check certain pairs and do "NOT XOR" on them.

The idea with the pairs is that if a row is symmetric, there are certain pairs that have to be equal. Noting that we zero index arrays, we have that within each row, the pairs will have indices 0 and 7, 1 and 6, 2 and 5, and 3 and 4. For the row to be symmetric, all 4 of those have to be matching pairs. In all, for the table to be symmetric, there are 32 pairs to check (the 4 pairs in each row, over 8 rows).

The trick with NOT XOR is that since XOR returns true iff the two are different, the negation of that statement returns true iff the two are the same.

So, if you wanted to do this entire check using only boolean operations, you'd take each of those pairs, (call it (a,b) for now) and do (NOT(a XOR b)) (!(a^b) in code), then AND the results of all 32 of those checks.

Granted, if I were actually doing this in code, I'd much rather just do a regular check for equality.