Geek Answers Handbook

Is it possible to have a rotation invariant identifier for a Boolean matrix?

Let's say I have a matrix of ones and zeros, and I would like the “identifier” for this matrix to take the same value regardless of whether the matrix rotates 90, 180 or 270 degrees, i.e. from 4 to -1. Ideally, this identifier should be 1/4 of the size of the matrix. Is it possible to write a function that performs this mapping?

Reference Information. I addressed this issue on a set of UVa issues. I do not need such a function to solve the problem, but it seems reasonable that it will exist, and its use will make a more elegant solution.

+6
algorithm matrix
source share
2 answers

Yes. You can take the original matrix A and rotate it to all possible configurations A ', A' 'and A' ''. Then you can sort them using your sort (just be sequential), select the first and hash using any hash function of your choice (again, the actual hash function doesn't matter, just be sequential).

Obviously, this can be optimized to a large extent without performing a full rotation and sorting - you can make comparisons lazily, stopping as soon as you know which rotation is sorted first - but the principle is the same.

+7
source share

You can just beat XOR all the turns that will be a symmetric identifier.

+1
source share

More articles:


All Articles