矩阵的就地换位

是否可以在原位置换一个(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]

来源

2012-02-10 UmNyobe

+14

这是可能的，但不平凡。像往常一样，维基百科有答案。 http://en.wikipedia.org/wiki/In-place_matrix_transposition – harold 2012-02-10 12:33:28

[前一段时间，我问了一个类似的问题，而不知道正确的术语]（http://stackoverflow.com/q/3009379/237483） – 2012-02-10 12:49:17

感谢Harold！我将制定一个实施并在此处发布。 – UmNyobe 2012-02-10 12:49:54

由Wikipedia - Following the cycles算法描述的启发，我提出了以下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

的就地矩阵转代表row-major ordering{0, 1, 2, 3, 4, 5, 6, 7}进4×2矩阵

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

transpose的参数m代表行大小，列大小由行大小和序列大小决定。该算法需要m×n位的辅助存储来存储信息，哪些元素已被交换。序列的索引映射下列方案：

在一般的映射函数为：

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，该过程继续进行，直到所有的循环都转换完毕。

来源

2012-02-16 22:51:44

这确实是正确的......但我无法弄清楚复杂性（坏情况是O（（mn）^ 3/2）的顺序） – UmNyobe 2012-03-16 14:50:30

引用维基百科：“已知算法的最坏情况线性方程计算代价为O（MN log MN）最好“ – 2012-03-16 20:14:37

你的依然高得多...无论如何，这是一个很好的答案 – UmNyobe 2012-03-17 08:45:28

问题是，该任务设置不正确。如果你的意思是“同一个地方”使用相同的矩阵，这是一个正确的任务。但是当你在谈论写入内存中的同一区域时，“矩阵被表示为一个大小为m * n的单个数组”，那么你必须添加它在那里表示如何。除此之外，只需要读取该矩阵的函数就可以进行任何更改 - 只需将其中的索引交换即可。

您想要在存储器中转置矩阵表示，以便通过索引对此矩阵的读取/设置功能保持不变。你不是吗？

此外，我们不能写下不知道的算法，是按行或列写入内存的矩阵。好吧，我们假设它是由行写的。不是吗？

如果我们设定这两个缺乏条件，任务就会变得正确并且不难解决。

简单，我们应采取矩阵中的每个元素通过线性指标，发现其行/列对，它移调，找到另一个导致线性指标，把值到新的地方。问题在于，只有在方矩阵的情况下，变换才是自动对称的，所以真的不能在现场完成。或者，如果我们找到整个索引转换映射并且稍后在矩阵上使用它，它可以。

开始矩阵A：
间行数
列的正数
纳米 - 元素
里的数 - 线性索引
I - 列号
的J - 行号

产生的矩阵B：
lir - 产生的线性指数

转化阵列反

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

这种自动调换具有意义仅当有在细胞重元素。

作为函数可以实现trans []数组。

来源

2012-02-15 08:48:34 Gangnus

相同的地方=相同的内存;转置=转置数据本身，而不是访问; mn = row1 | row2 | ... | rown =由行写入;到目前为止，你已经正确地说明了问题。现在你的算法是不正确的，正如我所说我已经尝试过你所提议的。尝试与[1,2,3]，[4,5,6]即在内存[1,2,3,4,5,6] – UmNyobe 2012-02-15 09:26:49

我已经使用这个算法在数千人使用的编。只是在某处你有一个错误。把代码放在这里。（我不坚持我没有和代码中的错误* * - 由内存写入） – Gangnus 2012-02-15 09:48:10

它只适用于矩形矩阵。即使算法背后的一般想法 – UmNyobe 2012-02-15 09:57:08

在一般情况下有效地做到这一点需要一些努力。非方形和内外位置算法有所不同。节省自己很多努力，只需使用FFTW。我先前准备了关于此事的a more complete write up，包括示例代码。

来源

2013-03-05 14:47:25

矩阵的就地换位

回答

相关问题