Looking for efficient algorithm to pick out a unique equivalence class representative for 2D arrays with lots of symmetries

Question

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.

Answer 1

Your problem is related to graph isomorphism, for which there is no known polynomial-time algorithm. Therefore, you should not expect any efficient algorithm that works on all cases.

In particular, your problem is GI-hard, so there is unlikely to be any efficient algorithm that works correctly on all problem instances (unless the matrices are quite small). In practice, you can use a software package like nauty, bliss, etc.

Why? Well, I will show that if there is a polynomial-time algorithm for your problem, then there is a polynomial-time algorithm for testing isomorphism of two bipartite graphs. It is known that the latter implies a polynomial-time algorithm for graph isomorphism. But no such algorithm is known, and it is a famous open problem whether such an algorithm exists. So don't hold your breath waiting for a polynomial-time algorithm for your problem, either.

Here is the reduction. Let $G_1,G_2$ be two bipartite graphs, and $A_1,A_2$ be their $n\times n$ adjacency matrices (here $n=|V_1|+|V_2|$). Then $G_1,G_2$ are isomorphic iff their adjacency matrices are equivalent up to row/column swaps. (You don't have to worry about permutations of the alphabet, since the alphabet is $\{0,1\}$, and a swap of 0/1 will increase the number of 1's in the adjacency matrix.) If we had a polynomial-time algorithm for your problem, we could apply it to $A_1,A_2$ to get their canonical representatives $R_1,R_2$; now $R_1=R_2$ iff $A_1,A_2$ are row/column-swap-equivalent, i.e., iff $G_1,G_2$ are isomorphic.

If you have to solve your problem in practice, you could use existing software tools for graph isomorphism, e.g., nauty, bliss, etc., to compute a canonical representative for the equivalence class under graph isomorphisms of the colored complete bipartite graph induced by your matrix. Specifically, if you have a $m\times m$ matrix $M$, then the corresponding bipartite graph has $2m$ vertices, with an edge from $i$ to $j$ carrying color $M[i,j]$ for each $i,j$.

See also https://math.stackexchange.com/q/159992/14578, https://mathoverflow.net/q/59991/37212, https://en.wikipedia.org/wiki/Graph_canonization.

Answer 2

If you are literally looping through all row permutations, and for each one looping through all column permutations, then you're spending at least $O(n!^2 \cdot poly(n))$ time on that; note that if you define the lexicographical order based on rows, so in your example 1,2,3,2,2,3 vs 1,1,2,1,3,2. Then you can do much better by simply iterating only over column permutations, and for each column permutation you don't need to loop over row permutations; once your columns are fixed just sort the rows lexicographically. This brings you down from $O(n!^2 \cdot poly(n))$ to $O(n! \cdot poly(n))$.

As you correctly suggest, you can assume without loss of generality that your first row will start with as many $1$s (or $0$s) as possible. That means that you don't even need to consider all column permutations, but only the ones that: make some row start with $M$ occurrences of the same digit where $M$ is maximized. So in particular, given there are only $31$ possible values, you can do:

for each $v \in \{0, ..., 31\}$:
 let $m_v$ be the maximum number of occurrences of $v$ in some row of the matrix.

let $S$ be the set of $v$'s that maximize $m_v$.
initialize $C = \emptyset$ as the set of the column permutations to try.
for each $v \in S$:
   let $R$ be the set of rows in which $v$ appears $m_v$ times.
      for each row $r \in R$:
         add to $C$ all the column permutations that leave all occurrences of $v$ at the beginning. 

This will likely give you a much smaller set of column permutations to try, although your parameters are small enough that it might end up wasting time in cases where the number of permutations to consider are not significantly reduced (e.g., some row contains only a single number).

For a more theoretical discussion, refer to this math stackexchange equivalent question.