Trasporre una matrice 1 dimensionale, che non rappresenta un quadrato, sul posto

Question

Questa domanda è simile a this, ma invece di una matrice che rappresenta un quadrato, ho bisogno di trasporre una matrice rettangolare.

Quindi, data una larghezza: x e un'altezza: y, il mio array ha elementi x * y.

Se la larghezza è 4 e l'altezza è 3, e ho:

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

che rappresenta la matrice:

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

Vorrei:

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

So per farlo creando un nuovo array, ma mi piacerebbe sapere come farlo sul posto come la soluzione per lo previously mentioned question.

Answer 1

Un modo per fare questo, è quello di spostare ogni elemento esistente della matrice origine nella nuova posizione, avendo cura di raccogliere la valu e all'inizio dell'indice di destinazione, in modo che possa anche essere spostato nella sua nuova posizione. Per una matrice NxM arbitraria, l'indice di destinazione di un elemento di indice X può essere calcolato come:

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

dove l'operatore "/" rappresenta la divisione intera (quoziente) e il "%" è l'operatore modulo (il resto) - Sto usando la sintassi di Python qui.

Il guaio è che non ti è garantito di attraversare tutti gli elementi della matrice se inizi in un punto arbitrario. Il modo più semplice per ovviare a questo problema consiste nel mantenere una bitmap di elementi che sono stati spostati nelle loro posizioni corrette.

Ecco po 'di codice Python che raggiunge questo:

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 

Ho sacrificato qualche ottimizzazione per chiarezza qui. È possibile utilizzare algoritmi più complicati per evitare la bitmap: dai un'occhiata ai riferimenti nel relativo documento Wikipedia article se si è seriamente intenzionati a risparmiare memoria al costo del calcolo.

Answer 2

Un modo semplice di trasporre in posizione è quello di ruotare ciascun elemento in posizione a partire dal retro della matrice. Hai solo bisogno di ruotare un singolo elemento al suo posto in un momento, così per l'esempio, a partire da [0,1,2,3,4,5,6,7,8,9,a,b], si ottiene: (. Questo dimostra gli elementi ruotati nella loro posizione finale su ogni passo)

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 

Se si scrive il numero di elementi da ruotare per ciascun elemento (dal retro al fronte), si ottiene una buona progressione. Per l'esempio (width= 4, height= 3):

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

Oppure, in modo leggermente migliore strutturato:

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

Rotazioni 1 elemento sono effettivamente presenti gabbie, ma la progressione porta ad una molto semplice algoritmo (in 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); 
     } 
    } 
}