Algorithmus zum Oktanten einer quadratischen Matrix alle sieben Möglichkeiten zu reflektieren

Question

In einer quadratischen Matrix der geraden Dimension s gibt es s/4(s/2+1) Arten von Quadraten, die auf sieben verschiedene Arten um die Matrix reflektiert werden können. Zum Beispiel wird eine 10 x 10-Matrix hat die einzigartigen Quadrate in der Figur unten gefärbt:

dieser 15 Plätze können um die horizontalen, vertikalen und diagonalen Achsen der Matrix in 7 verschiedene Weise reflektiert werden.

Angenommen, es gibt eindeutige Werte für jeden Typ eines solchen Elements eines n x n Arrays, wobei n eine gerade Zahl ist. Was ist der effizienteste Weg, die Matrix zu füllen (in C oder Java)? Mit anderen Worten, bei einer Liste von 15 Werten in einer beliebigen gewünschten Struktur müssen Sie den Rest des 10 x 10-Arrays mit den 15 Werten durch Reflexionen füllen. Was ist der schnellste Algorithmus, um dies zu tun?

Als Beispiel hier ist mein erster Versuch auf diesem (beachten Sie, dass es eine basierte Arrays verwendet):

public static int[][] valueSquare = new int[11][11]; 
public static int[][] valueSquareType = { 
     { 0, 40, 2, 12, 15, 20 }, 
     { 0, 2, 1, 4, 8, 12 }, 
     { 0, 12, 4, 25, 20, 15 }, 
     { 0, 15, 8, 20, 22, 18 }, 
     { 0, 20, 12, 15, 18, 0 }, 
}; 
static { 
    for(int x = 1; x <= 5; x++) for(int y = 1; y <= 5; y++) valueSquare[ 11 - x ][ y ] = valueSquareType[x][y]; 
    for(int x = 1; x <= 5; x++) for(int y = 1; y <= 5; y++) valueSquare[ 11 - x ][ 11 - y ] = valueSquareType[x][y]; 
    for(int x = 1; x <= 5; x++) for(int y = 1; y <= 5; y++) valueSquare[ x ][ 11 - y ] = valueSquareType[x][y]; 
} 

Ein Einwand gegen dieser ist, dass es einen redundanten Starter-Array, die 3 Möglichkeiten widerspiegeln , anstatt einer minimalen Starter-Array reflektiert 7 Wege. Idealerweise hätte ich gerne ein Starter-Array mit nur 15 Schlüsselwerten. Auch das Schleifen in meinem Versuch ist möglicherweise nicht der schnellste Ansatz.

Answer 1

Es sei denn, ich vermisse etwas, was schneller sein kann als das?

for (int i = 1; i < n/2; i++) { 
    for (int j = 0; j < i; j++) { 
     M[i][j] = M[j][i]; // first complete the first quadrant 
    } 
} 

for (int i = 0; i<n/2; i++) { 
    for (int j = n/2; j < n; j++) { 
     // then perform the three needed symmetries 
     M[i][j] = M[i][n-j-1]; 
     M[n-i-1][j] = M[i][n-j-1]; 
     M[n-i-1][n-j-1] = M[i][n-j-1]; 
    } 
} 

Answer 2

Angenommen, dies ist, was Sie meinen:

der schwarze Bereich in der oberen linken Ecke gegeben, dann müssen wir nur noch alle Elemente iterieren (i, j) in diesem Bereich und berechnen ihre Position in der andere Bereiche nach der Spiegelung (Diagonalen überlappen, so habe ich sie als grau markiert, aber die Formeln berücksichtigen sie auch und Sie können sie auch auf die gegebenen diagonalen Elemente anwenden):

Angenommen 0-Indexierung

(i, j) -> (i, n - j - 1)   # red area 
     -> (j, n - i - 1)   # yellow area 
     -> (j, i)     # teal area 
     -> (n - i - 1, j)   # green area 
     -> (n - i - 1, n - j - 1) # blue area 
     -> (n - j - 1, n - i - 1) # pink area 
     -> (n - j - 1, i)   # orange area 

Also iterieren Sie jedes gegebene schwarze Element und kopieren Sie es an die 7 Positionen in den anderen Bereichen. Beispiel:

#include <iostream> 

using namespace std; 

int v[6][6] = { 
     { 0, 3, 2, 12, 15, 20 }, 
     { 0, 2, 1, 4, 8, 12 }, 
     { 0, 12, 4, 25, 20, 15 }, 
     { 0, 15, 8, 20, 22, 18 }, 
     { 0, 20, 12, 15, 18, 0 }, 
}; 


int main() 
{ 
    int n = 6; 
    // iterate given black area: 
    for (int i = 0; i < n/2; ++i) 
    { 
     for (int j = i; j < n/2; ++j) 
     { 
      v[i][n - j - 1] = v[i][j]; // copy to red 
      v[j][n - i - 1] = v[i][j]; // copy to yellow 
      v[j][i] = v[i][j]; // copy to teal 
      v[n - i - 1][j] = v[i][j]; // copy to green 
      v[n - i - 1][n - j - 1] = v[i][j]; // copy to blue 
      v[n - j - 1][n - i - 1] = v[i][j]; // copy to pink 
      v[n - j - 1][i] = v[i][j]; // copy to orange; 
     } 
    } 

    for (int i = 0; i < n; ++i) 
    { 
     for (int j = 0; j < n; ++j) 
     { 
      cout << v[i][j] << " "; 
     } 
     cout << endl; 
    } 



    return 0; 
} 

Ausgang:

0 3 2 2 3 0 
3 2 1 1 2 3 
2 1 4 4 1 2 
2 1 4 4 1 2 
3 2 1 1 2 3 
0 3 2 2 3 0 

Welche, was Sie wollen zu sein scheint.

Answer 3

Zuerst würde ich denken, dass Sie die diagonale Reflexion machen. Dann haben Sie ein Viertel der Matrix gefüllt. Dies ist der schwierigste Teil, denke ich, weil jede Spalte eine andere Länge hat. Vielleicht so etwas wie folgt aus: 4 = s/2-1 und 10 = s

for(int j=0;j<4;j++) 
{ 
    for(int i=j;i<4;i++) 
    { 
    array[i+1][j]=array[j][i+1]; 
    } 
} 

Dann müssen Sie es nur in horizontal diagonal und spiegeln.

for(int j=0;j<5;j++) 
{ 
    for(int i=0;i<5;i++) 
    { 
    array[i][j]=array[9-i][j]; 
    } 
} 

und

for(int j=0;j<5;j++) 
{ 
    for(int i=0;i<10;i++) 
    { 
    array[i][j]=array[i][9-j]; 
    } 
} 

Wenn es einige Funktionen sind optimierter Speicher kopieren und drehen Sie sie, würden sie besser sein, aber ich weiß nicht. Für größere Matrizen wäre es nützlich, mehrere Threads (so viele wie Sie Kerne haben) zu verwenden. Bei dieser Größe bin ich mir nicht sicher, ob es helfen würde.

Answer 4

Geringe Abweichung von IVlads Antwort. Je nachdem, was Sie mit der aufgefüllten Matrix machen möchten, erlaubt Ihnen diese Version mit Zeigern, die Werte der "Starter-Arrays" zu variieren und sofort in den acht Oktanten reflektiert zu werden (siehe Beispiel). Ich gruppierte die Formeln in dem Beispiel, um zu zeigen, dass jeder Oktant auf vier Arten horizontal und vier Arten vertikal reflektiert werden kann, wobei die vertikalen Versionen eine einfache Transposition der Horizontalen sind, die is für j 's ist.

void showArray(int *arr[][8]) { 
    for (int i = 0; i < 8; ++i){ 
    for (int j = 0; j < 8; ++j) 
     cout << *arr[i][j] << " "; 
    cout << endl; 
    } 
} 

int main(){ 
    int d[10] = {0,1,2,3,4,5,6,7,8,9}; 
    int n = 8; int *v[8][8]; int k = 0; 

    for (int i = 0; i < n/2; ++i){ 
    for (int j = i; j < n/2; ++j){ 
     v[i][j] = &d[k]; 
     v[j][i] = &d[k]; 

     v[i][n - j - 1] = &d[k]; 
     v[j][n - i - 1] = &d[k]; 

     v[n - i - 1][j] = &d[k]; 
     v[n - j - 1][i] = &d[k]; 

     v[n - i - 1][n - j - 1] = &d[k]; 
     v[n - j - 1][n - i - 1] = &d[k]; 

     k++; 
    } 
    } 

    showArray(v); cout << endl; 
    d[2] = 44; 
    showArray(v); 
    return 0; 
} 

Ausgang:

0 1 2 3 3 2 1 0 
1 4 5 6 6 5 4 1 
2 5 7 8 8 7 5 2 
3 6 8 9 9 8 6 3 
3 6 8 9 9 8 6 3 
2 5 7 8 8 7 5 2 
1 4 5 6 6 5 4 1 
0 1 2 3 3 2 1 0 

0 1 44 3 3 44 1 0 
1 4 5 6 6 5 4 1 
44 5 7 8 8 7 5 44 
3 6 8 9 9 8 6 3 
3 6 8 9 9 8 6 3 
44 5 7 8 8 7 5 44 
1 4 5 6 6 5 4 1 
0 1 44 3 3 44 1 0