Given 2D arrays (number of rows between 0 and 10, number of columns between 0 and 10, elements are integers between 0 and 31) Two arrays $A,B$ are equivalent $A\sim B$ if $A$ can be transformed into $B$ via permutations of
- rows
- columns
- alphabet
e.g. $\begin{pmatrix} 1&2&3\\ 2&2&3 \end{pmatrix} \sim \begin{pmatrix} 1&1&2\\ 1&3&2 \end{pmatrix} $ by
- permuting the two rows
- permuting columns 1 and 2
- permuting the digits 2->1, 3->2, 1->3.
I am looking for an efficient algorithm to pick out a unique member for these equivalence classes for lookup in a cache table. Currently what I am doing is:
Loop through all permutations of rows
Loop through all permutations of colunms
Permute digits so that this array is lexicographically minimum (the first digit is 0, the next un-mapped digit is 1 etc). And taking the minimum (again, lexicographically) of these.
Obviously, one can improve on that by only considering as the first row any row that has the greatest multiplicity of characters. But I'm sure there is massive speedup to be had here. I am just not seeing a great way of finding it.
Edit
I want a function that is a many-to-one mapping of these 2D arrays to a representative of the equivalent class, i.e. all matrices that are equivalent are mapped to the same output. I want this operation to be quick, fewer operations is better.
Ideally each equivalence class can be mapped to a hashable object (like an integer or string) But if the output is a unique class representative that works too.