Is it possible to have a rotationally invariant identifier of a boolean matrix?

views:

answers:

+6 Q:

Is it possible to have a rotationally invariant identifier of a boolean matrix?

Say I have a matrix of ones and zeros, and I would like a 'identifier' for this matrix that takes the same value regardless of whether the matrix is rotated by 90, 180, or 270 degrees, i.e. a 4-to-1 mapping. Ideally, this identifier should be 1/4 the size of the matrix. Is it possible to write a function that does this mapping?

Background: I was looking at this problem on the UVa problem set. I don't exactly need such a function to solve the problem, but it seems reasonable that it would exist, and using it would make for a more elegant solution.

+7 A:

Yes. You can take your original matrix A, and rotate it to all the possible configurations A', A'' and A'''. You can then sort these using some sorting of your choosing (just be consistent) , pick the first, and hash that using any hash function of your choosing (again, the actual hash function doesn't matter, just be consistent).

Obviously this can be optimized heavily by not actually doing the full rotation and sorting - you can do the comparisons lazily, stopping as soon as you know which rotation sorts first - but the principle is the same.

Mark Byers 2009-11-28 15:19:14

or don't bother sorting but produce all 4 hashes and XOR them together. +1 for good idea!

Carl Smotricz 2009-11-28 15:22:26

Your idea would also work and it's simpler, but would probably be slower because it might be difficult to optimize this further. +1 for suggesting a different approach - sometimes simplicity is more important than performance.

Mark Byers 2009-11-28 15:29:00

@Carl: could you clarify how XOR-ing the 4 hashes will always produce a unique result?

int3 2009-11-28 15:33:16

A hash function isn't required to produce a unique result. A good hash function produces results roughly uniformly distributed over the hash result space, even when only small changes to the input are made. XORing two uniformly distributed variables will still be uniformly distributed.

Mark Byers 2009-11-28 15:37:56

Yeah, but I do need zero collisions for the UVa problem. I guess I should've mentioned that in the question.. but your method does produce a unique result, so that's cool (:

int3 2009-11-28 15:40:44

The result will be as unique as the 4 hashes. But what I think you're asking is how it will get the same result for all 4 rotations. The answer is that the XOR function is commutative, thus it won't matter in which order you provide the operands. In the course of 3 rotations (4 including none), you always come up with the same 4 hashes for a given matrix.

Carl Smotricz 2009-11-28 15:40:53

@int3 -- if you are expecting a hash function to always return a unique result, you're not thinking of hash functions properly. You should rather think of the hash function as producing a fingerprint, not necessarily unique, but one that will unfailing be the same when two things are identical. A hash function is (usually) a many to one map, not a one to one map.

tvanfosson 2009-11-28 15:41:23

It's hard to create unique instances in an object that's smaller than the one you're representing; if your matrix is 8 x 8 you'll have 64 bits of information, which you can't all encode in a single word. 2 solutions come to mind: No wait, I'm gonna submit this as an answer.

Carl Smotricz 2009-11-28 15:44:35

int3, given your requirement, your "hash" function should simply be "appending all N*N bits to make a N*N-bit integer".

Mark Byers 2009-11-28 15:48:36

Heh well.. I meant 'hash' in this case as a 4-to-1 mapping.. i.e. a perfect solution would be N*N bits -> N*N/4 bits. .. which your solution does satisfy! Sorry for the confusion caused.

int3 2009-11-28 16:05:51

Btw, I think my usage of 'hash' to mean 'mapping' isn't technically wrong.. just that it usually has other connotations. Also, UVa does list that problem under 'hashing / sets' ^^

int3 2009-11-28 16:21:58

You can just bit XOR all the rotations, that will be a symmetric identifier.

George Polevoy 2009-11-28 16:07:56

ansaurus

tags:

views:

answers:

Is it possible to have a rotationally invariant identifier of a boolean matrix?

related questions