就地换位矩阵 [英] In-place transposition of a matrix

问题描述

是否有可能转一个（M，N）基质就地，使该矩阵重新psented作为大小的单个阵列<$ $ P code> M *ñ？

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 甚而不存在。在一个单一的线路 矩阵垫[I] [J] =垫[我×M + D] ，其中反式[J] [我] =反[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]

推荐答案

在<一个启发href="http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices%3a_Following_the_cycles">Wikipedia - 继周期算法描述，我想出了下面的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

psented在行主序 重$ P $ {0，1， 2，3，4，5，6，7} 成4×2矩阵

0 4
1 5
2 6
3 7

再$ P由行主序psented $ {0，4，1，5，2，6，3，7} 。

重新$ P $的转参数 M psents的行大小，该columnsize ñ是由行大小和序列大小决定。该算法需要 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）​​模（M×N - 1）如果IDX＆LT; （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} 。每个周期可以调换独立于其它周期。变量周期最初指向第二个元素（第一次不需要移动，因为 0→0 ）。比特阵列参观保持已转置的元素和表示，该索引1（第二元件）需要移动。指标1被交换索引2（映射功能）。现在，索引1拥有指数2的元素，这个元素被交换与指数4.现在指数1的元素包含指数4的元素索引4的元素应该去索引1，它是在正确的地方，移调的周期结束，感动了所有的指标都被标记访问。变量周期被递增，直到第一个没有访问索引，这是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屋！