转置前导维度为 N 的一维数组

Question

如何在没有额外空间的情况下转置前导维度为 N 的一维数组？任何语言都可以

Answer 1

我的一维就地矩阵转置解决方案

  mn    = M*N;      /* M rows and N columns */

  q     = mn - 1;

  i = 0;      /* Index of 1D array that represents the matrix */

  do {

    k = (i*M) % q;

    while (k>i) k = (M*k) % q;

    if (k!=i) Swap(k, i);

  } while ( ++i <= (mn -2) );

  /* Update row and column */

  matrix.M = N;

  matrix.N = M;

Answer 2

将表示为线性数组的非方矩阵就地转置有点麻烦
的一个技巧。

这是一个 REXX 程序，它执行就地转置
用 1 表示的 2D 矩阵
大小为 M * N 的维数组，其中 M 是
行和
N 是其中的列数
非转置数组。转置后，M 变为列数，
N 成为行数。

i = 0                /* linear array index */ 
do j = 1 to N        /* j = 1 to columns of non-transposed array */ 
  do k = 1 to M      /* k = 1 to rows of non-transposed array */ 
    i = i + 1
    t = (k - 1) * N + j 
    do while t < i 
      jp = (t - 1) % M + 1 
      kp = t - (jp - 1) * M 
      t = (kp - 1) * N + jp 
    end 
    if i \= t then say 'exchange('i',' t')'   /* swap elements */
  end 
end

上面的程序显示了必须交换才能产生转置数组的数组元素。

该程序适用于任何
大小矩阵表示为元素排列的线性数组
按列然后按行。例如，M × N 矩阵的元素排列如下：

X_1,1, X_1,2, ... X_1,N , X_2,1, X_2,2, ... X_2,N, ... X_M,N

程序打印出需要交换的元素的线性数组索引以产生
如下形式的转置矩阵：

X_1,1, X_2,1, ... X_M,1, X _1,2, X_2,2, ... X_M,2, ... X_M,N

对于例如，从 M = 4、N = 2 和一个包含以下内容的数组开始：

A1, B1, A2, B2, A3, B3, A4, B4

执行以下交换：

exchange(2, 3) 
exchange(3, 5) 
exchange(4, 7) 
exchange(6, 7)

排列变为：

A1、A2、A3、A4、B1、B2、B3、B4

这是如何工作的？

从一个符号开始，将线性数组中的每个元素标识为：

X[i,j,k] 

where: i is the linear array index for an element in X 
       j is the row number for element in X
       k is the column number for element in X

使用此符号，行主要顺序的数组可以生成为：

i = 0 
do j = 1 to M    /* Row counter */ 
  do k = 1 to N  /* Column counter */ 
    i = i + 1     /* array index of element j, k */ 
    say 'X['i','j','k']' 
  end 
end

请注意，给定 j（行）和 k（列）、i 的值， X_i,j 的线性数组索引可以计算为：

i = (j - 1) * N + k 

矩阵 X 的转置是通过交换元素构造的
X[i,j,k]，其中 X[t,k,j] 在 j = 1 到 M 范围内，并且 >k = 1 到 N 假设 i > t。在
本质我们交换一切
行变量用于列变量。使用上述符号，这相当于
交换线性数组元素：

exchange(X[i,j,k], X[t,k,j])

给定 j 和 k 的值，我们可以计算 i 和 t 的值： ：

   i = (j - 1) * N + k
   t = (k - 1) * M + i

现在，随着 i 从 1 增加到 M * N，继续进行线性数组进行上述交换。
请注意，在每次迭代之后，X 中索引小于或等于 i 的所有元素都具有
被转置了。这是
因为只有当正确的元素已经存在时，每次迭代才会完成
交换为X[i]。

每当i>时t，这意味着先前的交换发生在索引t处。 t 处的元素是
如上所示进行交换，将其放置在某个新位置t^prime。给定一个
索引t，我们可以计算行主索引t^prime以及行和
与其关联的列号如下：

j^prime = (t - 1) % M + 1
k^素数 = t - (j^素数 - 1) * M
t^prime = (k^prime - 1) * N + j^prime

同样，如果t^prime 小于i，表示该元素被交换
我们也必须继续
进行另一轮计算。将 t 设置为计算出的 t^prime 并重复。最终，我会
变得小于t并且可以完成交换。基本上我们通过它的所有元素来跟踪该元素
之前的交换，直到我们在线性数组中的 i 或 i 的右侧找到它。

对线性数组中的每个元素重复此循环，矩阵将被转置。

Answer 3

最简单的方法就是：

for each m
  for each n
    if m != n 
       swap A[m][n] and A[n][m]

当然，这仅适用于方阵。对于矩形矩阵的就地转置，事情变得有点棘手。