Traspone una matrice senza buffer

Question

Traspone una matrice senza buffer

#1 da (8 voti)

4

Come è possibile trasporre una matrice MxN senza utilizzare una matrice "buffer"? In quest'ultimo caso è facile e abbastanza l'approccio "classico" ...

Dato un matrix[M][N] , vorrei inserirlo in una funzione void transpose_matrix(int matrix[][]) che opera direttamente sulla matrice passata come riferimento che, come già detto, modificherebbe lo spazio di memoria della matrice per trasporre i suoi elementi.

per esempio:

A =

1 2 3 4
5 6 7 8
9 1 2 3

A dopo la trasposizione (senza stampa carina) [1]:

1 5 9 2
6 1 3 7
2 4 8 3

Come sarebbe A in una matrice NxM :

Grazie!

[1]: stampa la matrice come se fosse in realtà una "nuova" NxM matrice.

c math matrices

posta peperunas 31.01.2015 - 09:33

fonte

1 risposta

Leggi altre domande sui tag c math matrices

Enum nelle dichiarazioni di switch java e completezza Come utilizzare più linguaggi di programmazione nello stesso programma? [chiuso]

score 8 · Accepted Answer

Operare in modo efficiente è complesso.

Wikipedia ha un bell'articolo sull'argomento: Trasposizione della matrice sul posto con molti riferimenti interessanti.

Una semplice implementazione C "follow-the-cycle" con O (1) requisito di memoria ausiliaria (e accessi di memoria pesantemente non consecutivi) è:

/// \param[in] m input matrix
/// \param[in] h number of rows of \a m
/// \param[in] w number of columns of \a m
///
/// Performs in-place transposition of matrix \a m.
void transpose(double m[], const unsigned h, const unsigned w)
{
  for (unsigned start = 0; start <= w * h - 1; ++start)
  {
    unsigned next = start;
    unsigned i = 0;
    do
    {
      ++i;
      next = (next % h) * w + next / h;
    } while (next > start);

    if (next >= start && i != 1)
    {
      const double tmp = m[start];
      next = start;
      do
      {
        i = (next % h) * w + next / h;
        m[next] = (i == start) ? tmp : m[i];
        next = i;
      } while (next > start);
    }
  }
}

È possibile trovare un'implementazione più veloce (C ++) che richiede l'archiviazione ausiliaria O (MN), un bit per elemento, qui (la trasposizione sul posto di una matrice domanda su Stackoverflow). Dai anche un'occhiata a Transpose una matrice 1 dimensionale, che non rappresenta un quadrato, in posizione .

PS in un certo numero di circostanze non è necessario o desiderabile riordinare fisicamente una matrice al suo ordinamento trasposto: potrebbe essere sufficiente fornire opzioni per specificare che determinate matrici devono essere interpretate in ordine trasposto.

Alcuni dettagli sull'algoritmo di cui sopra (assumendo la matrice di input A(3;4) della tua domanda):

Il primo blocco: ( do ... while ) è una sorta di generatore di sequenze:

next-sequence  start     next    i
-----------------------------------
[0]                0        0    1
[1,4,5,9,3]        1        1    5       <-
[2,8,10,7,6]       2        2    5       <-
[3,1]              3        1    1
[4,5,9,3]          4        3    3
[5,9,3]            5        3    2
[6,2]              6        2    1
[7,6]              7        6    1
[8,10,7]           8        7    2
[9,3]              9        3    1
[10,7]            10        7    1
[11]              11       11    1

Non tutte le sequenze sono utili:

sequenze di lunghezza 1 ( i == 1 e.g. [0] e [11] ) significano assenza di movimento dati e possono essere saltate;
sequenze in cui il valore finale di next è minore di start può essere saltato poiché sono sottosequenze di una sequenza già vista.

Il secondo blocco ( if ) eseguirà il movimento dei dati descritto da una sequenza.

es. [1,4,5,9,3] significa che il valore in posizione 4 passa alla posizione 1, il valore in posizione 5 passa alla posizione 4 ... mentre la posizione 1 passa alla posizione 3 (scritto utilizzando la notazione standard per cicli / permutazioni è (1 3 9 5 4) ).

Informazioni sull'espressione:

(position % h) * w + position / h;

questo è un modo per convertire la posizione tra l'originale e la matrice trasposta.