矩阵的就地转置 [英] In-place transposition of a matrix

问题描述

是否可以就地转置 (m,n) 矩阵，假设该矩阵表示为大小为 m*n 的单个数组?

Is it possible to transpose a (m,n) matrix in-place, giving that the matrix is represented as a single array of size m*n ?

常用算法

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

不适用于单个数组，除非矩阵是方阵.如果没有，最少需要多少额外内存?

doesn't apply to a single array unless the matrix is a square matrix. If none, what is the minimum amount of additional memory needed??

我已经尝试了所有口味的

I have already tried all flavors of

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

这是不正确的.在这个特定的例子中，m 甚至不存在.在一行中矩阵 mat[i][j] = mat[i*m + j]，其中 trans[j][i] = trans[i*n + j]

And it is not correct. In this specific example, m doesnt even exist. In a single line matrix mat[i][j] = mat[i*m + j], where trans[j][i] = trans[i*n + j]

推荐答案

灵感来自 维基百科 -遵循循环算法描述，我想出了以下C++实现:

Inspired by the Wikipedia - Following the cycles algorithm description, I came up with following C++ implementation:

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

程序对2×4矩阵进行就地转置

The program makes the in-place matrix transposition of the 2 × 4 matrix

0 1 2 3
4 5 6 7

以行主要排序表示 {0, 1, 2, 3, 4, 5, 6, 7} 到 4 × 2 矩阵

represented in row-major ordering {0, 1, 2, 3, 4, 5, 6, 7} into the 4 × 2 matrix

0 4
1 5
2 6
3 7

由行主序{0, 4, 1, 5, 2, 6, 3, 7}表示.

transpose的参数m代表rowsize，columnsizen由rowsize和sequence size决定.该算法需要m × n 位的辅助存储器来存储哪些元素已经交换过的信息.序列的索引按以下方案映射:

The argument m of transpose represents the rowsize, the columnsize n is determined by the rowsize and the sequence size. The algorithm needs m × n bits of auxiliary storage to store the information, which elements have been swapped. The indexes of the sequence are mapped with the following scheme:

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

一般的映射函数是:

idx → (idx × n) mod (m × n - 1) 如果 idx <(m × n), idx → idx 否则

idx → (idx × n) mod (m × n - 1) if idx < (m × n), idx → idx otherwise

我们可以在这个序列中识别出四个循环:{ 0 }, { 1, 2, 4 }, {3, 5, 6} 和 { 7 }.每个循环都可以独立于其他循环进行转置.变量 cycle 最初指向第二个元素(第一个元素不需要移动，因为 0 → 0).位数组 visited 保存已转置的元素并指示需要移动索引 1(第二个元素).索引 1 与索引 2(映射函数)交换.现在索引 1 保存索引 2 的元素，该元素与索引 4 的元素交换.现在索引 1 保存索引 4 的元素.索引 4 的元素应该转到索引 1，它在正确的位置，转置循环结束，所有触及的索引都被标记为已访问.变量 cycle 递增，直到第一个未访问的索引为 3.该过程继续此循环，直到所有循环都已转置.

We can identify four cycles within this sequence: { 0 }, { 1, 2, 4 }, {3, 5, 6} and { 7 }. Each cycle can be transposed independent of the other cycles. The variable cycle initially points to the second element (the first does not need to be moved because 0 → 0). The bit-array visited holds the already transposed elements and indicates, that index 1 (the second element) needs to be moved. Index 1 gets swapped with index 2 (mapping function). Now index 1 holds the element of index 2 and this element gets swapped with the element of index 4. Now index 1 holds the element of index 4. The element of index 4 should go to index 1, it is in the right place, transposing of the cycle has finished, all touched indexes have been marked visited. The variable cycle gets incremented till the first not visited index, which is 3. The procedure continues with this cycle till all cycles have been transposed.

这篇关于矩阵的就地转置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！