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

Question

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

Antecedentes: estaba mirando este problema en el conjunto de problemas UVa . No necesito exactamente esa 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 original A y rotarla a todas las configuraciones posibles A ', A' 'y A' ''. A continuación, puede ordenarlos utilizando algún tipo de selección de su elección (solo sea coherente), elija el primero y seleccione que utilizando cualquier función de hash de su elección (nuevamente, la función de hash real no importa, solo sea consistente).

Obviamente, esto se puede optimizar en gran medida al no hacer la rotación completa y la clasificación, puede hacer las comparaciones perezosamente, deteniéndose tan pronto como sepa qué rotación se ordena primero, pero el principio es el mismo.

Answer 2

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