Transponuj jednowymiarową tablicę, która nie reprezentuje kwadratu, w miejscu

Question

To pytanie jest podobne do this, ale zamiast tablicy reprezentującej kwadrat, muszę przetransponować prostokątną tablicę.

Tak więc, biorąc pod uwagę szerokość: x i wysokość: y, moja tablica ma elementy x * y.

Jeśli szerokość wynosi 4, a wysokość wynosi 3, a mam:

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

który reprezentuje macierz:

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

Chciałbym:

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

wiem jak aby to zrobić, tworząc nową tablicę, ale chciałbym wiedzieć, jak to zrobić w miejscu, takim jak rozwiązanie dla previously mentioned question.

Answer 1

Jednym ze sposobów, aby to zrobić, to przenieść każdy istniejący element oryginalnej matrycy do nowej pozycji, uważając, aby odebrać VALU e w punkcie docelowym jako pierwszy, aby można go było przenieść do nowej pozycji. Dla dowolnej matrycy NxM wskaźnik docelowy elementu o indeksie X może być obliczona jako:

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

gdzie operator „/” oznacza podział całkowitą (iloraz), a „%” to operator modulo (reszta) - używam tutaj składni Pythona.

Kłopot w tym, że nie masz pewności, że przemieścisz wszystkie elementy macierzy, jeśli zaczniesz od dowolnego miejsca. Najprostszym sposobem obejścia tego problemu jest zachowanie mapy bitowej elementów, które zostały przeniesione na właściwe pozycje.

Oto niektóre kodu Pythona, który osiąga w ten sposób:

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 

mam poświęcił kilka optymalizacji dla jasności tutaj. Możliwe jest użycie bardziej skomplikowanych algorytmów w celu uniknięcia bitmapy - zajrzyj do odnośników w odnośnym Wikipedia article, jeśli naprawdę poważnie myślisz o oszczędzaniu pamięci kosztem obliczeń.

Answer 2

Prostym sposobem transpozycji jest obracanie każdego elementu, zaczynając od tyłu matrycy. Wystarczy tylko obrócić pojedynczy element na miejsce w czasie, więc na przykład, wychodząc z [0,1,2,3,4,5,6,7,8,9,a,b], można uzyskać: (. To tylko pokazuje elementy obracane do ich ostatecznej pozycji na każdym kroku)

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 

Jeśli wypiszesz, ile elementów ma się obracać dla każdego elementu (od tyłu do przodu), tworzy on przyjemny postęp. Dla przykładu (width= 4, height= 3):

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

Lub, w nieco lepiej uporządkowany sposób:

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

Obroty 1 elementu są skutecznie no-ops, ale postęp prowadzi do bardzo prosta algorytm (w 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); 
     } 
    } 
}