Возможно ли иметь вращательно-инвариантный идентификатор булевой матрицы?

Question

Скажем, у меня есть матрица из единиц и нулей, и мне нужен «идентификатор» для этой матрицы, который принимает одно и то же значение независимо от того, повернута ли матрица на 90, 180 или 270 градусов, т.е.отображение 4 к 1.В идеале этот идентификатор должен составлять 1/4 размера матрицы.Можно ли написать функцию, которая выполняет это сопоставление?

Фон:я смотрел на Эта проблема по набору задач UVa.Мне не нужна такая функция для решения проблемы, но кажется разумным, что она существует, и ее использование может привести к более элегантному решению.

Answer 1

Да.Вы можете взять исходную матрицу A и повернуть ее во все возможные конфигурации A', A'' и A'''.Затем вы можете отсортировать их, используя какую-либо сортировку по вашему выбору (просто будьте последовательны), выберите первое и хешируйте его, используя любую хеш-функцию по вашему выбору (опять же, фактическая хеш-функция не имеет значения, просто будьте последовательны).

Очевидно, что это можно сильно оптимизировать, фактически не выполняя полное вращение и сортировку - вы можете выполнять сравнения лениво, останавливаясь, как только узнаете, какое вращение сортируется первым - но принцип тот же.

Answer 2

Вы можете просто бит XOR всех вращений, это будет симметричный идентификатор.