矩阵的就地转置

Question

是否可以(m,n)就地转置矩阵,并将矩阵表示为单个数组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];
      }
    }
 }

除非矩阵是方阵,否则不适用于单个数组.如果没有,所需的最小额外内存量是多少？

编辑:我已经尝试了各种口味的

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]

Answer 1

受维基百科的启发- 遵循循环算法描述,我提出了以下C++实现:

#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矩阵的就地矩阵转置

0 1 2 3
4 5 6 7

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

0 4
1 5
2 6
3 7

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

该参数m的transpose代表ROWSIZE,所述columnsize n由ROWSIZE和序列大小来确定.该算法需要m× n比特的辅助存储器来存储信息,哪些元素已被交换.序列的索引使用以下方案映射:

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否则

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