Il modo più veloce per verificare se due array 2D quadrati sono a rotazione e riflettenti distinti

Rompila in due problemi:

1. Come compareresti due array quadrati - chiamerò queste matrici - che non possono essere ruotati o riflessi, e
2. In che modo puoi confrontare un oggetto che può essere ruotato e riflettere su un altro elemento

Implementare il primo problema con un approccio ingenuo dà una risposta molto semplice - cammina le matrici in parallelo, fermandosi quando trovi valori non uguali. Se si cammina l'intera matrice senza valori non uguali, le matrici sono uguali. Camminare nella matrice, scorrere tra le colonne, anello interno attraverso ogni riga e confrontare i valori. Nota che camminare sulla matrice ci consente di enumerare tutti gli elementi della matrice come se fossero una singola raccolta lineare.

Per il secondo problema, ci sono otto modi diversi di ruotare e riflettere una matrice. Ci sono quattro angoli da usare come punto di partenza, e un algoritmo può camminare da ogni angolo in due direzioni (vale a dire orizzontalmente o verticalmente). Quindi dovremo eseguire il "problema 1" su ciascuna delle otto prospettive della matrice originale.

Come potrei implementarlo? Possiamo camminare le otto matrici in parallelo o in sequenza; Implementerò questo in modo sequenziale come potenzialmente più veloce (se la prima matrice controllata è una corrispondenza, non sono richiesti altri controlli) ma, cosa più importante, sarà più semplice.

Ciascuna delle otto matrici da controllare dovrebbe essere rappresentata da una funzione di camminata f(x) per recuperare il valore xth . Ad esempio, in n di n matrice quadrata 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];

e così via. Ora semplicemente,

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

Per ideare una strategia appropriata, è utile sapere come è probabile che l'input sia. Ad esempio, se hai array di grandi dimensioni pieni di zeri contenenti una mano di quelli, calcolare il checksum ti porterà rapidamente a risposte negative, ma se i tuoi array sono pieni di dati casuali, il checksum non sarà così utile, confrontando il primo coefficiente di solito sarà sufficiente per distinguere un array dall'altra.

I am wondering if there is more optimal solution than this brute-force approach?

Per l'input generale, non esiste una soluzione migliore. Tuttavia, si noti che è possibile evitare di copiare la matrice definendo una funzione di accesso personalizzata, ovvero una funzione che prende le coordinate nell'array e una delle nostre 16 permutazioni, nonché gli argomenti, per accedere alla matrice selezionata.

Potresti prendere in considerazione il calcolo di un checksum per un array e confrontare i checksum di due array.

I checksum sono indipendenti dall'ordine; se due array hanno checksum differenti, sicuramente non possono avere gli stessi elementi in una disposizione diversa (ad esempio ruotata).

Se devi confrontare le matrici più volte, puoi memorizzare le somme in cache e salvarle sul nuovo calcolo.

Dividi il tuo quadrato in 8 triangoli più piccoli. calcolare un hash / checksum su ciascuno di questi triangoli. Questo richiede solo un'iterazione sull'intero quadrato.

Ora, in modo che una certa simmetria sia presente, alcuni di questi triangoli devono essere uguali e quindi i loro valori hash. Quindi, se tutti hanno valori diversi, hai finito.

Altrimenti, confronta i triangoli con gli stessi valori di hash. Questo ti risparmia un po 'di tempo, ma è ovviamente un po' più complicato da implementare.