Thuật toán để phản ánh octant của ma trận vuông tất cả bảy cách

Question

Trong một ma trận vuông có kích thước chẵn s có s/4(s/2+1) loại hình vuông có thể được phản ánh theo bảy cách khác nhau xung quanh ma trận. Ví dụ, một ma trận 10 x 10 có hình vuông độc đáo màu trong hình bên dưới:

Những 15 ô vuông có thể được phản ánh xung quanh các trục ngang, dọc và đường chéo của ma trận trong 7 cách khác nhau.

Giả sử có các giá trị duy nhất được gán cho từng loại phần tử như vậy của mảng n x n trong đó n là số chẵn, cách hiệu quả nhất để điền ma trận (trong C hoặc Java) là gì? Nói cách khác, đưa ra một danh sách 15 giá trị trong bất kỳ cấu trúc nào bạn muốn, bạn cần phải cư trú phần còn lại của mảng 10 x 10 với 15 giá trị bằng phản xạ. Thuật toán nhanh nhất để làm điều này là gì?

Như một ví dụ, đây là lần thử đầu tiên của tôi tại đây (lưu ý rằng nó sử dụng mảng một-based):

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]; 
} 

Một phản đối này là nó có một mảng khởi động dự phòng được phản ánh 3 cách , thay vì một mảng khởi động tối thiểu phản ánh 7 cách. Lý tưởng nhất, tôi muốn một mảng khởi động, chỉ với 15 giá trị chính. Ngoài ra, vòng lặp trong thử của tôi có thể không phải là cách tiếp cận nhanh nhất.

Answer 1

Trừ khi tôi thiếu điều gì đó có thể nhanh hơn điều này?

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

Giả sử đây là những gì bạn có nghĩa là:

Với diện tích màu đen ở phía trên bên trái, sau đó chúng ta chỉ cần lặp tất cả các yếu tố (i, j) trong khu vực đó và tính toán vị trí của họ trong các khu vực khác sau khi phản chiếu (đường chéo chồng lên nhau nên tôi đánh dấu chúng là màu xám, nhưng các công thức cũng xem xét chúng và bạn cũng có thể áp dụng chúng cho các phần tử chéo đã cho):

Giả sử 0-indexing

(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 

Vì vậy hãy lặp lại từng phần tử màu đen và sao chép nó vào 7 vị trí trong các khu vực khác. Ví dụ:

#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; 
} 

Output:

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 

Mà dường như là những gì bạn đang sau.

Answer 3

Đầu tiên tôi nghĩ rằng bạn thực hiện phản xạ chéo. Sau đó, bạn có một quater của ma trận đầy. Đây là phần khó nhất tôi đoán vì mỗi cột có độ dài khác nhau. Có lẽ một cái gì đó như thế này: 4 = s/2-1 và 10 = s

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

Sau đó, bạn chỉ cần phải phản ánh nó trong theo đường chéo và theo chiều ngang.

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

và

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

Nếu có một số chức năng optimzed để sao chép bộ nhớ và lật nó, họ sẽ tốt hơn, nhưng tôi không biết bất kỳ. Đối với các ma trận lớn hơn, sẽ hữu ích khi sử dụng nhiều luồng (nhiều như bạn có lõi). Với kích thước này tôi không chắc chắn nó sẽ giúp đỡ.

Answer 4

Biến thể nhẹ về câu trả lời của IVlad. Tùy thuộc vào những gì bạn muốn làm với ma trận dân cư, phiên bản này với con trỏ cho phép bạn thay đổi bất kỳ giá trị "mảng khởi động" và xem nó ngay lập tức được phản ánh trong tám octants (xem ví dụ). Tôi nhóm các công thức trong ví dụ để chỉ ra rằng mỗi octant có thể được phản ánh theo bốn cách theo chiều ngang và bốn chiều theo chiều dọc, các phiên bản theo chiều dọc là một chuyển vị đơn giản của ngang, chuyển đổi i 's cho j' s.

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; 
} 

Output:

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