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

Question

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

Background: stavo guardando questo problema sul set di problemi UVa . Non ho esattamente bisogno di una tale funzione per risolvere il problema, ma sembra ragionevole che esista, e usarlo renderebbe una soluzione più elegante.

Answer 1

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

Ovviamente questo può essere ottimizzato pesantemente in realtà non eseguendo la rotazione e l'ordinamento completi - puoi fare i paragoni pigramente, fermandoti non appena sai quale rotazione ordina prima - ma il principio è lo stesso.

Answer 2

Puoi semplicemente bit XOR tutte le rotazioni, che sarà un identificatore simmetrico.