一個用於循環的矩陣的就地轉置

Question

我的老師問我們是否可以在C中使用一個「for循環」來轉置一個矩陣，並且我們不應該使用額外的空間（如將該矩陣運送到另一個陣列） 。該算法應該適用於非平方矩陣。這可能嗎？

編輯：「不應該使用額外的空間」我的意思是分配一個新的矩陣並複製矩陣的某些部分。這些是不允許的。

Answer 1

由於兩個矩陣的維數可能不同，所以矩陣的數據必須存儲在一維數組中。

（在C中，數據通常以行優先順序排列，使得對於rows - 行，cols -column矩陣，索引i對應於行r，柱c：i = r*cols + c索引從0開始，所以0 <= i < rows*cols ，0 <= c < cols，並0 <= r < rows相應地，索引i是在i/cols行，列i % cols，其中'％'是C模運算）

考慮一個矩陣是如何轉置，以及如何在存儲器中的數據順序的改變：。

2x2: A B = A B C D 
    C D 
    becomes 
    A C = A C B D 
    B D 

3x3: A B C = A B C D E F G H I 
    D E F 
    G H I 
    becomes 
    A D G = A D G B E H G F I 
    B E H 
    C F I 

對於所有矩形矩陣，只需將右上角三角形中的元素與左下角三角形中的相應元素交換即可。因此，對於一個 N× N方陣，您只需要 N（ N -1）/ 2掉期。 。

（單用i=0; i<cols*rows; i++循環足夠我上面顯示你如何計算行r和列c當你知道索引i，那麼你就可以計算出轉指數j = c*rows + r，並做交換，如果和僅當i < j。）

對於非正方形矩陣，情況類似，但交換更復雜。

2x3: A B C = A B C D E F 
    D E F 
    becomes 
    A D = A D B E C F 
    B E 
    C F 

3x4: A B C D = A B C D E F G H I J K L 
    E F G H 
    I J K L 
    becomes 
    A E I = A E I B F J C G K D H L 
    B F J 
    C G K 
    D H L 

如果我們假設我們有一個循環，通過數組前進一次，並執行或者沒有交換，或在更高的指數與元素的交換，這些交換偏移（0爲不交換，1用於交換下一個元素，2與下一個元素之後的元素交換，等等）形成一個整數序列。對於上述情況，這些序列是

2x3: 0 2 1 1 0 0 
3x4: 0 3 6 1 1 4 2 1 2 0 0 0 

換句話說，第一個元素沒有交換。對於2x3的情況，[1]處的元素與[1 + 2]處的元素交換; [2]處的元素與[2 + 1]處的元素交換;並且[3]處的元素與[3 + 1]處的元素交換。對於3x4的情況，[1]中的元素與[1 + 3]中的元素交換，[2]中的元素與[2 + 6]中的元素交換，[3]中的元素交換在[3 + 1]處的元素，等等。

這些交換序列關於矩陣尺寸是對稱的。也就是說，3x4和4x3矩陣的序列是相同的（這很有意義，真的，因爲我們在這裏做轉置）。

不幸的是，我不知道任何解析解或簡單的方法來生成的序列對於一般Ñ×中號矩陣。

（有些方法可以以某種形式重新生成交換表，但它們都需要一個與矩陣大小相同的輔助數組，幷包含每個元素的索引，並在此過程中進行更新。避免單獨的陣列/矩陣）。

因此，in-place matrix transpose與矩陣的元素單線性通過，每個元素最多一個交換，對於矩陣矩陣很容易。對於非正方形矩陣，只能在矩陣維數碰巧是交換單的情況下才能完成;截至2016年3月，通用公式或生成任何 N×M矩陣的方法都不知道。只是還不知道。

Answer 2

要換位矩陣，您需要交換矩陣內部的迭代。它可能使用基於exor操作的交換算法，允許在不使用額外存儲的情況下進行交換。

void swap(int *a, int *b) 
{ 
    *a = *a^*b; 
    *b = *a^*b; 
    *a = *a^*b;   
}