Transposition en place d'une matrice

Est-il possible de transposer un (m,n) de la matrice en place, ce qui donne la matrice est représenté par un tableau de taille m*n ?

L'habitude algorithme

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];
      }
    }
 }

ne s'applique pas à un seul tableau, sauf si la matrice est une matrice carrée.
Si aucun, quel est le montant minimum de la mémoire supplémentaire nécessaire??

EDIT:
J'ai déjà essayé toutes les saveurs de

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;
  }
}

Et il n'est pas correct. Dans cet exemple précis, m ne marche pas même exister. En une seule ligne
matrice mat[i][j] = mat[i*m + j], où trans[j][i] = trans[i*n + j]

source d'informationauteur UmNyobe

  1. 16

    Inspiré par le Wikipédia - en Suivant les cycles de description d'algorithme, je suis venu avec C++ suivant la mise en œuvre:

    #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, " "));
}

    Le programme met à la place de la matrice de transposition de la 2 × 4 de la matrice

    0 1 2 3
4 5 6 7

    représentés dans ligne-major de la commande {0, 1, 2, 3, 4, 5, 6, 7} dans le 4 × 2 de la matrice

    0 4
1 5
2 6
3 7

    représenté par la ligne-major de la commande {0, 4, 1, 5, 2, 6, 3, 7}.

    L'argument m de transpose représente la rowsize, le taillecolonne n est déterminé par le rowsize et la taille de la séquence. L'algorithme doit m × n bits d'auxiliaire de stockage pour stocker les informations, les éléments qui ont été échangés. L'index de la séquence sont mappés avec le schéma suivant:

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

    La fonction de mapping en général est:

    idx → (idx × n) mod (m × n - 1) si idx < (m × n), idx → idx sinon

    Nous pouvons identifier quatre cycles à l'intérieur de cette séquence: { 0 }{ 1, 2, 4 }{3, 5, 6} et { 7 }. Chaque cycle peut être transposé de façon indépendante des autres cycles. La variable cycle d'abord les points pour le second élément (le premier n'a pas besoin d'être déplacé en raison de 0 → 0). Le bit de la matrice de visited détient déjà transposé éléments et indique que l'indice de 1 (le deuxième élément) doit être déplacé. Indice 1 obtient échangé avec l'indice 2 (fonction de mapping). Maintenant indice 1 contient l'élément d'indice 2 et cet élément est échangé avec l'élément d'indice 4. Maintenant indice 1 contient l'élément d'indice 4. L'élément d'indice 4 devrait aller à l'index 1, il est au bon endroit, à la transposition de la fin du cycle, touché tous les indices ont été marquées visité. La variable cycle est incrémenté jusqu'à la première pas visité l'indice, qui est de 3. La procédure se poursuit avec ce cycle jusqu'à ce que tous les cycles ont été transposées.

  2. 2

    Le problème, c'est que la tâche est définie uncorrectly. Si vous entend-on par "au même endroit" utilisation de la matrice de même, c'est une bonne tâche. Mais, quand vous parlez de l'écriture en bas de la même zone dans la mémoire, "la matrice est représenté par un tableau de taille m*n", vous devez ajouter comment est-il représenté. Otherwards il suffit de ne rien changer à l'exception de la fonction qui lit que la matrice simplement permuter les indices.

    Vous souhaitez transposer la matrice de la représentation en mémoire donc, que la lecture de réglage/fonction pour cette matrice par des indices reste le même. N'est-ce pas?

    Aussi, on ne peut pas écrire l'algorithme ne pas savoir, est la matrice écrits dans la mémoire par lignes ou par colonnes. OK, disons que il est écrit par des rangées. N'est-ce pas?

    Si nous avons mis ces deux dépourvues de conditions, la tâche devient correct et n'est pas difficile à résoudre.

    Simplement nous devrions profiter de chaque élément dans la matrice par le linéaire de l'indice, de trouver sa ligne et sa colonne paire, transposer, trouver une autre résultant linéaire de l'indice et de mettre la valeur dans le nouveau lieu. Le problème est que la transformation est autosymmetric seulement dans le cas des matrices carrées, de sorte qu'il ne pouvait vraiment pas être fait dans le site. Ou il pourrait, si nous trouvons toute l'indice de transformation de la carte et à utiliser plus tard sur la matrice.

    Partir de la matrice A:

    m - nombre de lignes

    n - nombre de colonnes

    nm - nombre d'éléments

    li - linéaire de l'indice

    j' - numéro de la colonne

    j - numéro de ligne

    résultant de la matrice B:

    lir - résultant linéaire de l'indice de

    La transformation de la matrice de 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;
   }
}

    Tels auto transposition a de sens que s'il y a des éléments lourds dans les cellules.

    Il est possible de réaliser trans tableau[] en tant que fonction.

  3. 0

    Faire cela de manière efficace dans le cas général, nécessite un certain effort. Le non-carrés et contre l'out-of-place des algorithmes différents. Epargnez-vous beaucoup d'efforts et il suffit d'utiliser FFTW. J'ai déjà préparé une information plus complète écrirey compris des exemples de code, sur la question.