Est-il possible d'avoir un identifiant invariant par rotation d'une matrice booléenne?

Question

Disons que j'ai une matrice de uns et de zéros, et j'aimerais un "identifiant" pour cette matrice qui prend la même valeur, que la matrice soit tournée de 90, 180 ou 270 degrés, c'est-à-dire un 4-to -1 mappage. Idéalement, cet identifiant devrait être 1/4 de la taille de la matrice. Est-il possible d'écrire une fonction qui effectue ce mappage?

Contexte: Je regardais ce problème sur l'ensemble de problèmes UVa. . Je n’ai pas vraiment besoin d’une telle fonction pour résoudre le problème, mais il semble raisonnable qu’elle existe, et son utilisation constituerait une solution plus élégante.

Answer 1

Oui. Vous pouvez prendre votre matrice d'origine A et la faire pivoter vers toutes les configurations possibles A ', A' 'et A' ''. Vous pouvez ensuite les trier en utilisant le tri de votre choix (soyez juste cohérent), choisissez le premier et hachez-le en utilisant n'importe quelle fonction de hachage de votre choix (là encore, la fonction de hachage réelle n'a pas d'importance, soyez cohérente).

Évidemment, ceci peut être fortement optimisé en évitant de faire la rotation et le tri complets - vous pouvez faire les comparaisons paresseusement, en vous arrêtant dès que vous savez quelle rotation est triée en premier - mais le principe est le même.

Answer 2

Vous pouvez simplement mordre XOR toutes les rotations, ce sera un identifiant symétrique.