¿Es posible tener un identificador de invariante rotacional de una matriz booleana?

Question

Digamos que tengo una matriz de unos y ceros, y me gustaría un 'identificador' para esta matriz que toma el mismo valor independientemente de si la matriz se gira 90, 180 o 270 grados, es decir, un 4-to- 1 mapeo Idealmente, este identificador debe tener 1/4 del tamaño de la matriz. ¿Es posible escribir una función que haga este mapeo?

Antecedentes: Estaba mirando this problem en el paquete de problemas de UVa. No necesito exactamente tal función para resolver el problema, pero parece razonable que exista, y usarlo sería una solución más elegante.

Answer 1

Sí. Puede tomar su matriz A original y rotarla a todas las configuraciones posibles A ', A' 'y A' ''. A continuación, puede ordenarlos usando una selección de su elección (solo sea consistente), elija la primera y use la función hash que elija (de nuevo, la función hash real no importa, solo sea consistente).

Obviamente esto se puede optimizar en gran medida al no realizar la rotación y clasificación completas - puede hacer las comparaciones de forma perezosa, deteniéndose tan pronto como sepa qué rotación es la primera, pero el principio es el mismo.

Answer 2

Puede simplemente hacer un bit XOR de todas las rotaciones, que será un identificador simétrico.