È possibile avere un identificatore invariante a rotazione di una matrice booleana?

Question

Dire che ho una matrice di uno e zero, e vorrei un 'identificatore' per questa matrice che prende lo stesso valore indipendentemente dal fatto che la matrice sia ruotata di 90, 180 o 270 gradi, cioè un 4-to- 1 mappatura. Idealmente, questo identificatore dovrebbe essere 1/4 della dimensione della matrice. È possibile scrivere una funzione che esegue questa mappatura?

Sfondo: Stavo guardando this problem sul set di problemi UVa. Non ho esattamente bisogno di una tale funzione per risolvere il problema, ma sembra ragionevole che esisterà, e utilizzarlo sarebbe una soluzione più elegante.

Answer 1

Sì. Puoi prendere la matrice A originale e ruotarla su tutte le possibili configurazioni A ', A' 'e A' ''. Puoi quindi ordinarli usando una sorta di ordinamento a tua scelta (solo essere coerente), scegli il primo e l'hash che usa qualsiasi funzione di hash di tua scelta (di nuovo, la funzione di hash effettiva non ha importanza, basta essere coerenti).

Ovviamente questo può essere ottimizzato pesantemente da non effettivamente facendo il giro completo e ordinamento - si può fare il confronto pigramente, fermandosi non appena si sa che tipo di rotazione prima - ma il principio è lo stesso.

Answer 2

È possibile solo un bit XOR per tutte le rotazioni, che sarà un identificatore simmetrico.