使用一个 for 循环就地转置矩阵

Question

我的老师问我们是否可以在 C 中仅使用一个 "for loop" 转置一个矩阵，我们不应该使用额外的 space（比如将矩阵转移到另一个数组）。该算法应该适用于非方阵。这可能吗？

编辑："shouldn't use extra space" 我的意思是分配一个新矩阵并复制矩阵的某些部分。这些是不允许的。

Answer 1

要转置矩阵，您需要交换矩阵内部的项。可以使用基于 exor 操作的交换算法，该算法允许在不使用额外存储的情况下进行交换。

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

Answer 2

因为两个矩阵的维度可以不同，所以矩阵的数据必须存储在一维数组中。

（在 C 中，数据通常按行优先顺序排列，因此对于 rows 行、cols 列矩阵，索引 i 对应行 r，列 c：i = r*cols + c。索引从零开始，因此 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++ 的单个 for 循环就足够了。我在上面展示了当您知道索引 [=15= 时如何计算行 r 和列 c ]；然后您可以计算转置索引 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 矩阵的序列是相同的（这很有意义，因为我们在这里进行转置）。

不幸的是，我不知道有任何闭合形式的表达式或简单的方法来生成一般 N×M 矩阵的序列.

(有一些方法可以以某种形式重新生成交换table，但它们都需要一个与矩阵大小相同的辅助数组，包含每个元素的索引，并沿途更新它。这违背了避免单独 array/matrix.)

的目的

因此，in-place matrix transpose 对矩阵的元素进行一次线性传递，每个元素最多交换一次，对于方矩阵来说很容易。对于非方阵，只有当矩阵维度恰好是你有交换顺序的维度时才能这样做；截至 2016 年 3 月，还不知道任何 N×M 矩阵的通用公式或生成方法。注意，并非不可能；只是还不知道。

使用一个 for 循环就地转置矩阵

In-place transposition of a matrix with one for loop

c

transpose

loops

matrix