La forma más rápida de verificar si dos matrices 2D cuadradas son rotacionales y reflectivas distintas

7

La mejor idea que tengo hasta ahora es rotar la primera matriz en {0, 90, 180, 270} grados y reflejarla horizontal y / o verticalmente. Básicamente obtenemos 16 variaciones [1] de la primera matriz y las comparamos con la segunda matriz. si ninguno de ellos coincide, las dos matrices son rotacional y reflectivamente distintas.

Me pregunto si hay una solución más óptima que este enfoque de fuerza bruta?

[1]

0deg, no reflection
0deg, reflect over x
0deg, reflect over y
0deg, reflect over x and y
90deg, no reflection
...
    
pregunta Žan Kusterle 11.11.2013 - 15:50

4 respuestas

1

Divida esto en dos problemas:

  1. ¿Cómo compararías dos matrices cuadradas? Llamaré a estas matrices , que no se pueden rotar ni reflejar, y
  2. ¿Cómo compararías un elemento que se puede rotar y reflejar contra otro elemento?

Implementar el primer problema con un enfoque ingenuo da una respuesta muy simple: recorra las matrices en paralelo, deteniéndose una vez que encuentre valores no iguales. Si recorres toda la matriz sin valores no iguales, las matrices son iguales. Para recorrer la matriz, recorra en bucle las columnas, el bucle interior a través de cada fila y compare valores. Tenga en cuenta que recorrer la matriz nos permite enumerar todos los elementos de la matriz como si fueran una única colección lineal.

Para el segundo problema, hay ocho formas diferentes de rotar y reflejar una matriz. Hay cuatro esquinas que deben usarse como punto de partida, y un algoritmo puede caminar desde cada esquina en dos direcciones (es decir, horizontal o verticalmente). Por lo tanto, tendremos que realizar el "problema 1" en cada una de las ocho perspectivas de la matriz original.

¿Cómo implementaría esto? Podemos recorrer las ocho matrices en paralelo o secuencialmente; Implementaré esto secuencialmente como potencialmente más rápido (si la primera matriz verificada es una coincidencia, no se requieren otras comprobaciones) pero lo más importante será que sea más simple.

Cada una de las ocho matrices que se deben verificar debe estar representada por una función de desplazamiento f(x) para recuperar el valor xth . Por ejemplo, en un n por n array cuadrado A ,

f1(x) = A[x % n, x / n]; // walking rows first, then columns
f2(x) = A[x / n, x % n]; // walking columns first, then rows

// using a different starting point
f3(x) = A[n - (x / n), x % n];
f4(x) = A[n - (x % n), x / n];

y así sucesivamente. Ahora simplemente,

foreach walking function
    foreach value in walking function
        if value not equal to corresponding value in target 
            next walking function
    return true // not non-equal values found
return false // none of the functions matched
    
respondido por el Kirk Broadhurst 18.11.2013 - 17:17
3

Para diseñar una estrategia adecuada, es útil saber cómo es probable que sea la entrada. Por ejemplo, si tiene arreglos grandes llenos de ceros que contienen una mano de unos, entonces calcular la suma de control lo llevará rápidamente a respuestas negativas, pero si sus arreglos están llenos de datos aleatorios, la suma de comprobación no será tan útil, comparando el primer coeficiente Por lo general, será suficiente para distinguir una matriz de la otra.

  

Me pregunto si hay una solución más óptima que este enfoque de fuerza bruta?

Para información general, no hay mejor solución. Sin embargo, tenga en cuenta que puede evitar copiar la matriz definiendo un descriptor de acceso personalizado, es decir, una función que toma coordenadas en la matriz y una de nuestras 16 permutaciones, así como argumentos, para acceder a la matriz seleccionada.

    
respondido por el user40989 18.11.2013 - 16:27
2

Podría considerar calcular una suma de comprobación para una matriz y comparar las sumas de comprobación de dos matrices.

Las sumas de comprobación son independientes del orden; si dos matrices tienen diferentes sumas de comprobación, definitivamente no pueden tener los mismos elementos en una disposición diferente (por ejemplo, rotada).

Si tiene que comparar arrays muchas veces, puede almacenar las sumas y guardarlas en el nuevo cálculo.

    
respondido por el 9000 11.11.2013 - 16:29
2

Divide tu cuadrado en 8 triángulos más pequeños. calcula un hash / checksum en cada uno de estos triángulos. Esto solo requiere una iteración en toda la casilla.

Ahora, para que esté presente alguna simetría, algunos de estos triángulos deben ser iguales, y por lo tanto sus valores hash. Por lo tanto, si todos los valores son diferentes, habrá terminado.

De lo contrario, compare los triángulos solo con los mismos valores hash. Esto le ahorra tiempo, pero, por supuesto, es un poco más difícil de implementar.

    
respondido por el Per Alexandersson 11.11.2013 - 18:42

Lea otras preguntas en las etiquetas