Возможно ли иметь вращательно-инвариантный идентификатор булевой матрицы? - PullRequest
6 голосов
/ 28 ноября 2009

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

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

Ответы [ 2 ]

7 голосов
/ 28 ноября 2009

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

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

1 голос
/ 28 ноября 2009

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...