0
$\begingroup$

Here, n = no. of rows and m = no. of columns

Suppose, there are three matrices - A[3][2] : {{1,2},{3,4},{5,6}} ; B[3][2] : {{1,2},{3,4},{5,6}} ; C[3][2] : {{2,1},{3,4},{5,6}} . Here A=B , A!=C and B!=C .

So, task is to check equality between all possible combinations of 2-dimensional matrices from a given set of matrices with time complexity less than O(n^m) .Here the possible combinations are (A,B) , (A,C) and (B,C).

( As part of the solution :

Matrix to matrix comparison is costly .So these matrices have to be converted into 'something' which results less comparison time . I think if I can convert/represent the matrix as a value/string/1-dimensional array , then equality comparison will be less costlier . My question is how to convert/represent ? If it can be solved by hashing how to solve this exactly ? )

NOTE : No. of 2-dimensional matrices and their sizes are not fixed. In my problem scenario no. of 2-dimensional matrices are been generated gradually which can be of any size. Cant predict how many matrices of which size will be generated . Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

$\endgroup$
3
  • $\begingroup$ What is $n$? How many matrices are there? What is the size of the matrices? Are they dense/sparse? $\endgroup$ – orlp Mar 4 '20 at 10:33
  • $\begingroup$ I have edited my question. Please check it . @orlp $\endgroup$ – ssarmah Mar 4 '20 at 12:09
  • 1
    $\begingroup$ You are asking whether two matrices can be checked for equality in less than $O(nm)$ time (which is trivially impossible without preprocessing) but it sounds more like your actual problem is to partition matrices into equivalence classes by equality (which would normally be solved by hashing, which reduces the number of equality comparisons that need to be performed). $\endgroup$ – Aaron Rotenberg Mar 4 '20 at 14:29
2
$\begingroup$

Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

It seems it would be easiest to store the previously seen matrices in a Trie. You can then test whether the given input matrix is equal to any of the previous matrices in $O(nm)$, regardless of how many previous matrices there are. This is the best you can do, since you must examine each element of the matrix at least once. You can't get an individual comparison to run faster than $O(mn)$, but you can test for equality among the entire set faster.

$\endgroup$
0
$\begingroup$

Can't be done. If you compare $A$ and $B$ (both $m \times n$), if you compare less than $m \cdot n$ elements, the matrices can differ in the elements not compared. If you want to compare $A$ to a set of $r$ $B$ matrices, you'll have to compare against all of them, i.r. $m \cdot n \cdot r$ comparisons. Maybe some smart preprocessing of the $B$ matrices can cut down the factor $r$ for the comparison of $A$ to the set of $B$s, but doing that won't be cheap. If you suspect most of the time they aren't equal, a fingerprint (i.e., a hash like SHA265) of the elements of the $B$ will tell you cheaply which ones can't be equal to $A$, but you'll have to check for equality.

$\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.