矩陣的就地換位

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

由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 

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

transpose的參數m代表行大小，列大小由行大小和序列大小決定。該算法需要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，該過程繼續進行，直到所有的循環都轉換完畢。

Answer 2

問題是，該任務設置不正確。如果你的意思是「同一個地方」使用相同的矩陣，這是一個正確的任務。但是當你在談論寫入內存中的同一區域時，「矩陣被表示爲一個大小爲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 []數組。

Answer 3

在一般情況下有效地做到這一點需要一些努力。非方形和內外位置算法有所不同。節省自己很多努力，只需使用FFTW。我先前準備了關於此事的a more complete write up，包括示例代碼。