5

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

4

3 回答 3

3

我的一维原位矩阵转置解决方案

  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;
于 2011-06-24T11:13:41.237 回答
2

就地转置表示为线性数组的非方阵有点技巧。

这是一个 REXX 程序，它执行在大小为M * N的一维数组中表示的 2D 矩阵的就地转置，其中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的转置是通过在j = 1 到 M和k = 1 到 N的范围内将元素 X[i,j,k]与X[t,k,j]交换来构造的，前提是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素数= (t - 1) % M + 1
k素数= t - (j素数- 1) * M
t素数= (k素数- 1) * N + j素数

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

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

于 2010-08-18T17:17:06.757 回答
1

最简单的方法就是：

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

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

于 2010-04-02T19:10:11.867 回答