Chuyển một mảng 1 chiều, không đại diện cho một hình vuông, tại chỗ

Question

Câu hỏi này tương tự như this, nhưng thay vì một mảng đại diện cho một hình vuông, tôi cần phải chuyển đổi một mảng hình chữ nhật.

Vì vậy, với chiều rộng: x và chiều cao: y, mảng của tôi có các phần tử x * y.

Nếu chiều rộng là 4 và chiều cao là 3, và tôi có:

{0,1,2,3,4,5,6,7,8,9,10,11} 

đại diện cho các ma trận:

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

Tôi muốn:

{0,4,8,1,5,9,2,6,10,3,7,11} 

tôi biết làm thế nào để làm điều đó bằng cách tạo một mảng mới, nhưng tôi muốn biết cách thực hiện nó như một giải pháp cho previously mentioned question.

Answer 1

Một cách để thực hiện việc này, là di chuyển từng phần tử hiện có của ma trận ban đầu sang vị trí mới, cẩn thận để nhận valu e tại chỉ mục đích đầu tiên, để nó cũng có thể được di chuyển đến vị trí mới của nó. Đối với một ma trận NxM tùy ý, chỉ số điểm đến của một phần tử tại chỉ số X có thể được tính như sau:

X_new = ((N*X)/(M*N)) + ((N*X) % (M*N)) 

nơi "/" nhà điều hành đại diện cho phân chia số nguyên (quotient) và "%" là toán tử modulo (phần còn lại) - Tôi đang sử dụng cú pháp Python ở đây.

Sự cố là bạn không được đảm bảo duyệt qua tất cả các phần tử trong ma trận nếu bạn bắt đầu tại vị trí tùy ý. Cách dễ nhất để giải quyết vấn đề này là duy trì một bitmap các phần tử đã được di chuyển đến đúng vị trí của chúng.

Dưới đây là một số mã Python mà đạt được điều này:

M = 4 
N = 3 
MN = M*N 

X = range(0,MN) 

bitmap = (1<<0) + (1<<(MN-1)) 
i = 0 

while bitmap != ((1<<MN) - 1): 
    if (bitmap & (1<<i)): 
     i += 1 
     xin = X[i] 
     i = ((N*i)/MN) + ((N*i) % MN) 
    else: 
     xout = X[i] 
     X[i] = xin 
     bitmap += (1<<i) 
     i = ((N*i)/MN) + ((N*i) % MN) 
     xin = xout 

print X 

tôi đã hy sinh một số tối ưu hóa cho rõ ràng ở đây. Có thể sử dụng các thuật toán phức tạp hơn để tránh bitmap - hãy xem các tham chiếu trong số Wikipedia article liên quan nếu bạn thực sự nghiêm túc về việc tiết kiệm bộ nhớ với chi phí tính toán.

Answer 2

Cách đơn giản để chuyển vị trí là xoay từng phần tử vào vị trí bắt đầu từ mặt sau của ma trận. Bạn chỉ cần xoay một yếu tố duy nhất vào vị trí cùng một lúc, ví dụ như vậy, bắt đầu với [0,1,2,3,4,5,6,7,8,9,a,b], bạn nhận được: (. Điều này chỉ cho thấy các yếu tố xoay vào vị trí cuối cùng của họ trên mỗi bước)

0,1,2,3,4,5,6,7,8,9,a,b, // step 0 
        ,b, // step 1 
      ,8,9,a,7, // step 2 
     4,5,6,8,9,a,3,  // step 3 
       ,a,  // step 4 
     ,8,9,6,   // step 5 
    ,4,5,8,9,2,   // step 6 
     ,9,    // step 7 
    ,8,5,    // step 8 
,4,8,1,     // step 9 
    ,8,     // step 10 
,4,      // step 11 
0,      // step 12 

Nếu bạn viết ra có bao nhiêu phần tử để xoay cho mỗi phần tử (từ sau ra trước), nó tạo thành một tiến trình tốt đẹp. Đối với ví dụ (width= 4, height= 3):

1,4,7,1,3,5,1,2,3,1,1,1 

Hoặc, theo một cách hơi có cấu trúc tốt hơn:

1,4,7, 
1,3,5, 
1,2,3, 
1,1,1 

Xoay của 1 phần tử là một cách hiệu quả không-ops, nhưng sự tiến triển dẫn đến một rất đơn giản thuật toán (trong C++):

void transpose(int *matrix, int width, int height) 
{ 
    int count= width*height; 

    for (int x= 0; x<width; ++x) 
    { 
     int count_adjustment= width - x - 1; 

     for (int y= 0, step= 1; y<height; ++y, step+= count_adjustment) 
     { 
      int last= count - (y+x*height); 
      int first= last - step; 

      std::rotate(matrix + first, matrix + first + 1, matrix + last); 
     } 
    } 
}