Ist es möglich, eine rotationsinvariante Kennung einer boolean Matrix zu haben?

Question

Sagen, ich habe eine Matrix aus Einsen und Nullen, und ich möchte ein ‚Bezeichner‘ für diese Matrix, die den gleichen Wert annimmt, unabhängig davon, ob die Matrix um 90 gedreht wird, 180 oder 270 Grad, dh um ein 4- -1-Mapping. Idealerweise sollte diese Kennung 1/4 der Größe der Matrix sein. Ist es möglich, eine Funktion zu schreiben, die diese Zuordnung funktioniert?

Hintergrund: Ich war auf der Suche auf dieses Problem auf dem UVa Problem Satz . Ich weiß nicht genau brauchen eine solche Funktion, das Problem zu lösen, aber es scheint vernünftig, dass es vorhanden ist, und es mit wäre für eine elegantere Lösung machen.

Answer 1

Ja. Sie können Ihre ursprüngliche Matrix A nehmen, und drehen Sie ihn auf alle möglichen Konfigurationen A ‚A‚‘und A‚‘‘. Diese können Sie dann mit einiger Sortierung Ihrer Wahl sortieren (nur konsequent sein), die erste Wahl und dass Hash jede Hash-Funktion Ihrer Wahl verwenden (auch hier die tatsächliche Hash-Funktion keine Rolle spielt, nur konsequent sein).

Natürlich kann dies stark optimiert werden, indem nicht tatsächlich die vollständige Rotation zu tun und Sortieren - Sie können die Vergleiche lazily tun können, zu stoppen, sobald Sie wissen, welche Rotation Sorten erste -. Aber das Prinzip ist das gleiche

Answer 2

Sie können die Drehungen nur alle Bit XOR, das wird ein symmetrischer Bezeichner sein.