Trasposizione sul posto di una matrice

Question

È possibile trasporre una matrice (m,n) sul posto, fornendo che la matrice sia rappresentata come una singola matrice di dimensione m*n?

L'algoritmo solito

transpose(Matrix mat,int rows, int cols){ 
    //construction step 
    Matrix tmat; 
    for(int i=0;i<rows;i++){ 
     for(int j=0;j<cols;j++){ 
     tmat[j][i] = mat[i][j]; 
     } 
    } 
} 

non si applica ad un singolo array meno che la matrice è una matrice quadrata. Se nessuno, qual è la quantità minima di memoria aggiuntiva necessaria ??

EDIT: Ho già provato tutte le versioni di

for(int i=0;i<n;++i) { 
    for(int j=0;j<i;++j) { 
    var swap = m[i][j]; 
    m[i][j] = m[j][i]; 
    m[j][i] = swap; 
    } 
} 

E non è corretto. In questo specifico esempio, m non esiste nemmeno. In una riga singola matrice mat[i][j] = mat[i*m + j], dove trans[j][i] = trans[i*n + j]

Answer 1

ispirato dalla descrizione Wikipedia - Following the cycles algoritmo, sono venuto con seguente C attuazione ++:

#include <iostream> // std::cout 
#include <iterator> // std::ostream_iterator 
#include <algorithm> // std::swap (until C++11) 
#include <vector> 

template<class RandomIterator> 
void transpose(RandomIterator first, RandomIterator last, int m) 
{ 
    const int mn1 = (last - first - 1); 
    const int n = (last - first)/m; 
    std::vector<bool> visited(last - first); 
    RandomIterator cycle = first; 
    while (++cycle != last) { 
     if (visited[cycle - first]) 
      continue; 
     int a = cycle - first; 
     do { 
      a = a == mn1 ? mn1 : (n * a) % mn1; 
      std::swap(*(first + a), *cycle); 
      visited[a] = true; 
     } while ((first + a) != cycle); 
    } 
} 

int main() 
{ 
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; 
    transpose(a, a + 8, 4); 
    std::copy(a, a + 8, std::ostream_iterator<int>(std::cout, " ")); 
} 

Il programma rende la matrice trasposizione sul posto del 2 × 4 matrice

0 1 2 3 
4 5 6 7 

rappresentato in row-major ordering{0, 1, 2, 3, 4, 5, 6, 7} nella matrice 4 × 2

0 4 
1 5 
2 6 
3 7 

rappresentato dall'ordine di riga principale {0, 4, 1, 5, 2, 6, 3, 7}.

L'argomento m di transpose rappresenta il rowsize, il columnize n è determinato dal rowsize e dalla dimensione della sequenza. L'algoritmo richiede m × n bit di memoria ausiliaria per archiviare le informazioni, quali elementi sono stati scambiati. Gli indici della sequenza sono mappati con il seguente schema:

0 → 0 
1 → 2 
2 → 4 
3 → 6 
4 → 1 
5 → 3 
6 → 5 
7 → 7 

La funzione di mappatura in generale è:

idx → (idx × n) mod (m × n - 1) se idx < (m × n), idx idx → altrimenti

possiamo identificare quattro cicli all'interno di questa sequenza: { 0 }, { 1, 2, 4 }, {3, 5, 6} e { 7 }. Ogni ciclo può essere trasposto indipendentemente dagli altri cicli. La variabile cycle inizialmente punta al secondo elemento (il primo non deve essere spostato perché 0 → 0). Il bit-array visited contiene gli elementi già trasposti e indica che l'indice 1 (il secondo elemento) deve essere spostato. L'indice 1 viene scambiato con l'indice 2 (funzione di mappatura). Ora l'indice 1 contiene l'elemento di indice 2 e questo elemento viene scambiato con l'elemento di indice 4. Ora l'indice 1 contiene l'elemento di indice 4. L'elemento di indice 4 deve andare all'indice 1, è nel posto giusto, trasporre del ciclo è terminato, tutti gli indici toccati sono stati contrassegnati come visitati. La variabile cycle viene incrementata fino al primo indice non visitato, che è 3. La procedura continua con questo ciclo fino a quando tutti i cicli sono stati trasposti.

Answer 2

Il problema è che l'attività è impostata in modo errato. Se intendessi per "lo stesso posto" usare la stessa matrice, è un compito corretto. Ma quando si parla di scrivere nella stessa area in memoria, "la matrice è rappresentata come una singola matrice di dimensioni m * n", è necessario aggiungere come è rappresentato. Altrimenti è sufficiente cambiare nulla tranne la funzione che legge quella matrice, semplicemente scambiare gli indici in essa.

Si desidera trasporre la rappresentazione della matrice nella memoria in modo che la funzione di lettura/impostazione per questa matrice per indici rimanga la stessa. Non è vero?

Inoltre, non è possibile annotare l'algoritmo non sapendo, è la matrice scritta in memoria da righe o colonne. OK, diciamo è scritto dalle righe. Non è vero?

Se impostiamo queste due condizioni mancanti, l'attività diventa corretta e non è difficile da risolvere.

Semplicemente dovremmo prendere ogni elemento della matrice per indice lineare, trovare la sua coppia di righe/colonne, trasporlo, trovare un altro indice lineare risultante e inserire il valore nella nuova posizione. Il problema è che la trasformazione è autosimmetrica solo nel caso di matrici quadrate, quindi in realtà non poteva essere eseguita sul sito. Oppure potrebbe, se troviamo l'intera mappa di trasformazione dell'indice e successivamente usarla su matrice.

partire matrice A:
m- numero di righe
numero di colonne n-
nm - numero di elementi
li - indice lineare
i - colonna numero
j - numero di riga

matrice risultante B:
lir - indice lineare risultante

matrice Transforming trans

//preparation 
for (li=0;li<nm;li++){ 
    j=li/n; 
    i=li-j*n; 
    lir=i*m+j; 
    trans[li]=lir; 
} 

// transposition 
for (li=0;li<nm;li++){ 
    cur=li; 
    lir=trans[cur]; 
    temp2=a[lir]; 
    cur=lir; 
    while (cur!=li){ 
     lir=trans[cur]; 
     temp1=a[cur]; 
     a[cur]=temp2; 
     temp2=temp1; 
     check[cur]=1; 
     cur=lir; 
    } 
} 

Tale trasposizione auto ha senso solo se vi sono elementi pesanti nelle cellule.

È possibile realizzare l'array trans [] come una funzione.

Answer 3

Fare questo in modo efficiente nel caso generale richiede qualche sforzo. Gli algoritmi non quadrati e inversi fuori posto differiscono. Risparmia molti sforzi e usa semplicemente FFTW. Ho preparato in precedenza a more complete write up, incluso il codice di esempio, sull'argomento.