É possível ter um identificador rotacionalmente invariante de uma matriz de boolean?

Question

dizer que tenho uma matriz de uns e zeros, e gostaria de um 'identificador' para esta matriz que leva o mesmo valor independentemente do facto da matriz é rodado de 90, 180, ou 270 graus, isto é, uma 4-a -1 mapeamento. Idealmente, este identificador deve ser 1/4 do tamanho da matriz. É possível escrever uma função que faz esse mapeamento?

Fundo: Eu estava olhando para este problema no set problema UVa . Eu não precisa exatamente essa função para resolver o problema, mas parece razoável que existiria, e usá-lo faria para uma solução mais elegante.

Answer 1

Sim. Você pode ter a sua matriz A original, e girá-lo para todas as configurações possíveis A 'A '' e A '''. Você pode então classificar estes usando alguma classificação de sua escolha (apenas ser consistente), escolher o primeiro, e de hash que o uso de qualquer função hash de sua escolha (novamente, a função hash real não importa, basta ser consistente).

Obviamente, isso pode ser otimizado fortemente por não realmente fazendo a rotação completa e classificação - você pode fazer as comparações preguiçosamente, parando assim que você sabe que tipo de rotação em primeiro lugar -., Mas o princípio é o mesmo

Answer 2

Você pode apenas mordeu XOR todas as rotações, que vai ser um identificador simétrica.