4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you for the clear problem statement. Don't use "EDIT". Instead, revise the question so it is self-contained and reads well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755 $\endgroup$
    – D.W.
    Jul 21 at 17:33
  • $\begingroup$ Is the answer by @D.W. here (cs.stackexchange.com/questions/161198/…) not enough? $\endgroup$ Jul 21 at 17:56
  • $\begingroup$ @BernardoSubercaseaux, that one only allows permutations of the columns and alphabet remapping, but not permutations of the rows. (The problem statement on that one is a bit challenging to follow, so I hope I have that right.) I believe that makes a big difference. $\endgroup$
    – D.W.
    Jul 21 at 18:47
  • $\begingroup$ I should have taken that other question down, you are right. It was a different question because I found a way to exploit more symmetries in my problem statement. But they are quite similar. @DW that is precisely right. In the other problem the symmetry group was S_C x S_D (where C is column, and D is digits, and S is the permutation group) Here we have additionally S_R. $\endgroup$ Jul 21 at 23:51

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ My first thought also was about graph isomorphism, but note that you don't swap the same columns and the rows, so it's not quite the same. For these constraints (10 rows/columns), the polytime solution is not a requirement. I agree with OP that some clever hash/canonical representation is probably the way to go. $\endgroup$
    – Dmitry
    Jul 21 at 19:00
  • $\begingroup$ @Dmitry, I understand, but I already took that into account. Check my reduction again; my reduction handles that. Note that for a bipartite graph, you can separately swap rows and columns (don't have to be the same ones) of the adjacency matrix. $\endgroup$
    – D.W.
    Jul 21 at 19:02
  • $\begingroup$ Got it, I didn't understand at first why you talked about bipartite graphs. $\endgroup$
    – Dmitry
    Jul 21 at 21:57
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh, thanks for the link. That is indeed a very similar question. $\endgroup$ Jul 21 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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