Similar multidimensional array detection

Question

I'm looking for some sort of algorithm so I can quickly identify similar matrices, the matrices are not stored permanently so I'd need a way of mapping each matrix to an easily stored values, after which I can use the same mapping on future matrices and quickly compare against the calculated values.

The way I'm defining a similar matrix is simply whether or not they are identical when mirrored by vertical line, horizontal line, major diagonal and minor diagonal.

For example

1 2 3
4 5 6
7 8 9

is identified as the same as all the following matrices

I've been stumped on this problem for days now, the matrices aren't stored permanently therefore comparing them directly isn't possible. Could anyone point me in the right direction? Thanks

To understand it right, you are looking for an hash value for a matrix, and you are expecting your hash function to produce values in an equivalence class, for your definition of similarity. Let me ask couple of properties of a matrix? Is it always square, filled with positive integers, etc. — Umut Kahramankaptan, May 26 '15 at 05:25
Yeah that sounds about right. The matrices are always square and they consist of values 0-7. — rhysw, May 26 '15 at 06:32
Can I insert the following into the same equivalence class? [7 4 1, 8 5 2, 9 6 3] [9 8 7, 6 5 4, 3 2 1] [3 6 9, 8 5 2, 1 4 7] And what is your average size of the matrix? For a 3*3 matrix it might not be feasible to store even one hash, depending on the size of the hash. — Umut Kahramankaptan, May 26 '15 at 10:05
What amount of data can you afford to store par matrix ? Given that you have 8^9 distinct matrix and that your definition of similarity splits that in 4, a non lossy approach would need at least 25 bits of storage per matrix. What's your storage system ? Also, what's the question that you need to answer when you encounter a new matrix ? "do I already encountered this matrix or similar ?", "when was the first time I encountered this matrix or similar ?", "what was the form of the first matrix similar to this one?" — Clément Prévost, May 26 '15 at 18:51

score 1 · Answer 1 · answered May 26 '15 at 19:14

1

Calculate a hash value for each of the eight symmetric matrixes and keep only the smallest of them - that should do the trick. This gives you the same value for each matrix of an equivalence class.

answered May 26 '15 at 19:14

Doc Brown

199,015
33
367
565

Umut Kahramankaptan · Answer 2 · 2015-05-26T12:07:28.733

Instead of storing one hash value, store 5 hash values

M0= 1 2 3
    4 5 6
    7 8 9

is identified as the same as all the following matrices

Operations which creates M1 to M4 are written below

M1= 3 2 1  (vertical mirror  M1:= VM(M0) )
    6 5 4
    9 8 7
-----
M2= 7 8 9 (horizontal mirror M2:= HM(M0) )
    4 5 6
    1 2 3
-----
M3= 1 4 7 (transpose M3= T(M0) )
    2 5 8
    3 6 9
-----
M4=     9 6 3 (M4= VM(T(MO) )
    8 5 2
    7 4 1

all your equivalent matrices (total 7 in addition to the original) can be written as combinations of VM(), HM(), and T().

so if you hold 8 hash values for a matrix, you can compare your hash values.

To calculate a hash value of the matrix M0 (numbers are only digits in your case), you can convert it to the string "123456789" and use a hash function.

I hope this helps.

score 0 · Answer 3 · answered May 26 '15 at 10:54

You can use mathematics to identify similarity. I have assumed each example you have given after the initial matrix for similarity as condition.

For the matrix in your example -

Let Ux = 1 2 3
         4 5 6
         7 8 9

Let Ix = 0 0 1
         0 1 0
         1 0 0

If you perform the matrix multiplication of Ux and Ix you would obtain -

Ux . Ix = 3 2 1
          6 5 4
          9 8 7

Which is condition 1.

If you do

Ix . Ux = 7 8 9
          4 5 6
          1 2 3

Which is condition 2. So, you could use Ix to identify two conditions of similarity you have defined.

For the condition 3 it is Transpose(Ux).

For the condition 4 it is Trasnpose(Ix . Ux . Ix).

Hope this helps!

score 0 · Answer 4 · answered May 26 '15 at 21:08

Based on some back-of-the-envelope thinking, I would suggest the following approach: If you sum each individual row, each column, each diagonal, and the 4 corners, you will obtain a set of 9 numbers, which can then be sorted. This sorted list of numbers will be identical for all the cases you listed and their rotations, but should be unique (i.e., not collide with any other arrangements). If this analysis is true, you could use a trivial hash function of that 9-number list as your stored value.

(Of course, if rotations are excluded from your similarity classification, then I will have to go back to the drawing board.)

Similar multidimensional array detection

4 Answers4