Ist es möglich, einen rotationsinvarianten Bezeichner einer booleschen Matrix zu haben?

Question

Angenommen, ich habe eine Matrix aus Einsen und Nullen, und ich hätte gerne einen "Bezeichner" für diese Matrix, der denselben Wert annimmt, unabhängig davon, ob die Matrix um 90, 180 oder 270 Grad gedreht ist. 1 Zuordnung Idealerweise sollte diese Kennung 1/4 der Größe der Matrix betragen. Ist es möglich, eine Funktion zu schreiben, die diese Zuordnung durchführt?

Hintergrund: Ich schaute this problem auf dem UVa-Problem-Set. Ich brauche eine solche Funktion nicht unbedingt, um das Problem zu lösen, aber es scheint vernünftig, dass es existieren würde, und ihre Verwendung würde eine elegantere Lösung ermöglichen.

Answer 1

Ja. Sie können Ihre ursprüngliche Matrix A nehmen und sie auf alle möglichen Konfigurationen A ', A' 'und A' '' drehen. Sie können diese dann sortieren, indem Sie eine Sortierung Ihrer Wahl verwenden (seien Sie einfach konsistent), wählen Sie die erste aus und hashen Sie diese mit einer beliebigen Hash-Funktion Ihrer Wahl (die eigentliche Hash-Funktion spielt dabei keine Rolle).

Offensichtlich kann dies stark optimiert werden, indem nicht die volle Rotation und Sortierung durchgeführt wird - Sie können die Vergleiche träge machen und stoppen, sobald Sie wissen, welche Rotation zuerst sortiert - aber das Prinzip ist das gleiche.

Answer 2

Sie können nur ein bisschen XOR alle Rotationen, das wird eine symmetrische Kennung sein.