Cómo recuperar una matriz barajada.

Question

Supongamos que tengo una matriz $A$. $A$ puede ser una clasificación de la matriz. Es decir, $A(i,j)$ es la calificación de usuario $i$ ha dado a la partida $j$.

Supongamos que se me revuelven las filas y columnas de la matriz $A$ y consigue $A_{\text{shuffle}}$.

Ahora, en realidad, ambos $A$ $A_{\text{shuffle}}$ contiene la misma información. Debido a la mezcla de columnas o filas que, de no cambiar las calificaciones de los usuarios dan a los elementos.

Es allí una manera eficiente de mostrar que $A$ $A_{\text{shuffle}}$ contienen los mismos usuarios y elementos.

I. e., como sugiere polkjh, dadas las matrices de $A$$B$, ¿cómo puedo comprobar de manera eficiente si $B$ puede ser obtenida mediante la transposición de filas y columnas de $A$?

Gracias

Answer 1

Ese es el problema NP sobre el isomorfismo gráfico. ¿Qué tipo de algoritmo consideras "eficientemente"? ¿Algún polinomio algo? Seguro que puedes usar algunas heurísticas, si sabes algo sobre$A$, pero no hay algo polinómico para el caso general.

Answer 2

Vamos a reformular la pregunta:

Si$A,B$ son dos matrices del mismo tamaño (no necesariamente cuadradas) sobre algún alfabeto, decida si hay matrices de permutación$P,Q$ de manera que$A = PBQ$.

Aunque no recuerdo una referencia precisa en el momento, estoy bastante seguro de que este problema es NP-completo, lo que significa que no existe un algoritmo eficiente para este problema (suponiendo que P$\neq$ NP).