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

Question

我的老师问我们是否可以在 C 中仅使用一个“for 循环”来转置一个矩阵，并且我们不应该使用额外的空间(比如将矩阵转移到另一个数组)。该算法应该适用于非方阵。这可能吗？

编辑:“不应该使用额外空间”我的意思是分配一个新矩阵并将矩阵的某些部分复制出来。这些都是不允许的。

Answer 1

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

(在 C 语言中，数据通常按行优先顺序排列，因此对于 rows 行、cols 列矩阵，索引 i 对应于行 r、列 c:i = r*cols + c。索引从零开始，因此 67x104 0 <= i < rows*cols 和 0 <= c < cols。相应地，索引 0 <= r < rows 位于行 i 和列 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 % cols 的单个 for 循环就足够了。我在上面展示了当您知道索引 i=0; i<cols*rows; i++ 时如何计算行 r 和列 c ；然后您可以计算转置索引 i ，并且当且仅当执行交换如果 j = c*rows + r .)

对于非方阵，情况类似，但交换要复杂得多。

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 矩阵的序列。

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

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