0
$\begingroup$

Let's say that I have $14$ regular matrices of order $4$. I'd like to compare the data of each matrix with all 13 others to see if there's a match

Is there an algorithm that can accomplish this task?

I'm more interested in the algorithm and not any particular programming language.

[EDIT] In response to the first comment, a match would be if all rows and columns of the matrix are the same, small 2x2 example.

 m1       m5
|00| === |00|
|00|     |00|

 m3       m1
|00| =\= |00|
|01|     |00|

 m2       m1
|10| =\= |00|
|01|     |00|

 m2       m4
|10| === |10|
|01|     |01|

It would continue like this for 16x16 but in the end I could get a list of matrix that maches m1 matches m5 m2 matches m4 m1 doesn't match m3, etc...

$\endgroup$
1
  • $\begingroup$ Please provide an example of what is and isn't a match. If A(2,3) equals D(4,4) is that a match? $\endgroup$
    – Phil Sweet
    Jul 27 '19 at 20:31
1
$\begingroup$

Brute force:

for (i1=0; i1<array.len-1; i1+=1)
    for (i2=i1+1; i2<array.len; i2+=1)
        if (same(array[i1], array[i2]))
            print(i1, "matches", i2)

where same(a,b) compares the two matrices.

Optimization:

This is an order N² algorithm, so for very large values of "14" and "4" you'd want to optimize the process.

Some possibilities (I'm sure there are others, and perhaps better):

  • Create a vector of the checksums of each matrix, and call same() only when the two elements have the same value. This is still N² in the worst case, but in practice would potentially have far fewer comparisons.

  • Do the same thing, but first sort the checksum vector to group elements with the same value together. Then make comparisons only within each group. (You'd also have to track the original position of each matrix in order to display the answer.)

  • I don't know what the elements of a matrix are, but if they are well ordered (e.g. the set of three items, "rock", "paper", "scissors" isn't), you could sort the array (order N log(N)) and then a linear pass could find the consecutive equal arrays.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.