M x N大小的原地（固定空间）矩阵转置 | 更新
原文： https://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/
一个新职位大约有四个月的缺口（缺少 GFG）。 给定一个M x N矩阵，请在不使用辅助存储器的情况下转置该矩阵。 使用辅助数组很容易转置矩阵。 如果矩阵大小对称，我们可以通过在二维对角线上镜像二维数组来对矩阵进行原位转置（尝试一下）。 如何在适当位置转置任意大小的矩阵？ 参见下面的矩阵，
a b c a d g j
d e f ==> b e h k
g h i c f i l
j k l
根据 C/C++ 中的 2D 编号，相应的位置映射如下所示：
Org element New
0 a 0
1 b 4
2 c 8
3 d 1
4 e 5
5 f 9
6 g 2
7 h 6
8 i 10
9 j 3
10 k 7
11 l 11
请注意，第一个和最后一个元素保留在其原始位置。 我们可以很容易地看到变换形成了很少的排列周期。
-
1 -> 4 -> 5 -> 9 -> 3 -> 1― 总共 5 个元素组成一个循环 -
2 -> 8 -> 10 -> 7 -> 6 -> 2– 循环中还有 5 个元素 -
0 – 自循环
-
11 – 自循环
从上面的示例中，我们可以轻松设计一种算法来沿着这些循环移动元素。 如何生成置换周期？ 这两个矩阵中的元素数是恒定的，由N = R * C给出，其中R是行数，C是列数。 位置or（R x C矩阵中的旧位置）的元素移至nl（C x R矩阵中的新位置）。 我们需要建立ol, nl, r和c之间的关系。 假设ol = A[or][oc]。 在 C/C++ 中，我们可以将元素地址计算为：
ol = or x C + oc (ignore base reference for simplicity)
它应移至转置矩阵中的新位置nl，例如nl = A[nr][nc]或 C/C++ 术语。
nl = nr x R + nc (R - column count, C is row count as the matrix is transposed)
观察nr = oc和nc = or，因此将其替换为nl，
nl = oc x R + or -----> [eq 1]
解决ol和nl之间的关系后，我们得到：
ol = or x C + oc
ol x R = or x C x R + oc x R
= or x N + oc x R (from the fact R * C = N)
= or x N + (nl - or) --- from [eq 1]
= or x (N-1) + nl
要么，
nl = ol x R - or x (N-1)
请注意，nl和ol的值永远不会超出N-1，因此请考虑在两侧进行模除以（N-1），我们根据同余性得到以下结果：
nl mod (N-1) = (ol x R - or x (N-1)) mod (N-1)
= (ol x R) mod (N-1) - or x (N-1) mod(N-1)
= ol x R mod (N-1), since second term evaluates to zero
nl = (ol x R) mod (N-1), since nl is always less than N-1
好奇的读者可能已经注意到上述关系的重要性。 每个位置的缩放比例为R（行大小）。 从矩阵中可以明显看出，每个位置都由R的比例因子位移。实际的乘数取决于N-1的同余类，即乘数可以是同等类的-ve和+ve值。 因此，每个位置变换都是简单的模除法。 这些模除法形成循环排列。 我们需要一些簿记信息来跟踪已经移动的元素。 这是原地矩阵转换的代码，
// Program for in-place matrix transpose
#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128
using namespace std;
// A utility function to print a 2D array of size nr x nc and base address A
void Print2DArray(int *A, int nr, int nc)
{
for(int r = 0; r < nr; r++)
{
for(int c = 0; c < nc; c++)
printf("%4d", *(A + r*nc + c));
printf("\n");
}
printf("\n\n");
}
// Non-square matrix transpose of matrix of size r x c and base address A
void MatrixInplaceTranspose(int *A, int r, int c)
{
int size = r*c - 1;
int t; // holds element to be replaced, eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while (i < size)
{
cycleBegin = i;
t = A[i];
do
{
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%(N-1)
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
}
while (i != cycleBegin);
// Get Next Move (what about querying random location?)
for (i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
// Driver program to test above function
int main(void)
{
int r = 5, c = 6;
int size = r*c;
int *A = new int[size];
for(int i = 0; i < size; i++)
A[i] = i+1;
Print2DArray(A, r, c);
MatrixInplaceTranspose(A, r, c);
Print2DArray(A, c, r);
delete[] A;
return 0;
}
输出：
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
1 7 13 19 25
2 8 14 20 26
3 9 15 21 27
4 10 16 22 28
5 11 17 23 29
6 12 18 24 30
扩展：2013 年 3 月 17 日 – 一些读者确定了矩阵转置和字符串转换之间的相似性。 没有太多理论，我提出了问题和解决方案。 在给定的元素数组中，例如[a1b2c3d4e5f6g7h8i9j1k2l3m4]。 将其转换为[abcdefghijklm1234567891234]。 该程序应在原地运行。 我们需要的是原位转置。 下面给出的是代码。
#include <stdio.h>
#include <iostream>
#include <bitset>
#define HASH_SIZE 128
using namespace std;
typedef char data_t;
void Print2DArray(char A[], int nr, int nc) {
int size = nr*nc;
for(int i = 0; i < size; i++)
printf("%4c", *(A + i));
printf("\n");
}
void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) {
int size = r*c - 1;
data_t t; // holds element to be replaced, eventually becomes next element to move
int next; // location of 't' to be moved
int cycleBegin; // holds start of cycle
int i; // iterator
bitset<HASH_SIZE> b; // hash to mark moved elements
b.reset();
b[0] = b[size] = 1;
i = 1; // Note that A[0] and A[size-1] won't move
while( i < size ) {
cycleBegin = i;
t = A[i];
do {
// Input matrix [r x c]
// Output matrix
// i_new = (i*r)%size
next = (i*r)%size;
swap(A[next], t);
b[i] = 1;
i = next;
} while( i != cycleBegin );
// Get Next Move (what about querying random location?)
for(i = 1; i < size && b[i]; i++)
;
cout << endl;
}
}
void Fill(data_t buf[], int size) {
// Fill abcd ...
for(int i = 0; i < size; i++)
buf[i] = 'a'+i;
// Fill 0123 ...
buf += size;
for(int i = 0; i < size; i++)
buf[i] = '0'+i;
}
void TestCase_01(void) {
int r = 2, c = 10;
int size = r*c;
data_t *A = new data_t[size];
Fill(A, c);
Print2DArray(A, r, c), cout << endl;
MatrixTransposeInplaceArrangement(A, r, c);
Print2DArray(A, c, r), cout << endl;
delete[] A;
}
int main() {
TestCase_01();
return 0;
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2016 年 7 月 9 日更新：有关空间复杂性和存储顺序的说明。
很长一段时间后，碰巧要审查此帖子。 当我们使用位集作为标记（代码中的哈希）时，一些读者提出了一些有效的问题，关于它如何就位（？）。 通过查看标题或内容来对错误的理解表示歉意。 在准备初始内容时，我正在考虑使用至少需要转置矩形矩阵的O(MN)辅助空间来实现朴素的实现。 上面显示的程序使用恒定空间，因为位集大小在编译时是固定的。 但是，为了支持矩阵的任意大小，我们需要位集大小至少为O(MN)大小。 可以使用哈希映射（摊销的O(1)复杂度）标记完成的位置，但哈希映射最坏的情况是O(n)或O(log n)基于实现。 哈希映射的空间成本也会根据插入的项目而增加。 *请注意，原位使用。 矩阵空间。
同样，假设矩阵将以行主要顺序（存储器中的连续位置）存储。 如果矩阵是用编程语言（例如 Fortran / Julia）以列的主要顺序表示的，则读者可以得出公式。
感谢那些指出了这两个空白的读者。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
该帖子不完整，没有提及两个链接。
1. Aashish 在循环前导算法后面介绍了很好的理论。 请参阅他关于字符串转换的文章。
2. Sambasiva 像往常一样展示了他在递归问题上的非凡技巧。 确保了解他的解决方案。
版权属于：月萌API www.moonapi.com，转载请注明出处
