5

余分なスペースなしで、先頭の次元Nの1d配列を転置するにはどうすればよいですか？どの言語でも構いません

4

3 に答える 3

3

1D インプレース行列転置の私のソリューション

  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

線形配列として表された非正方行列をその場で転置するのはちょっとしたトリックです。

以下は、サイズM * Nの 1 次元配列で表される 2D 行列のインプレース転置を実行する REXX プログラムです。ここで、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 に増加するにつれて、上記の交換を行う線形配列を進めます。各反復の後、 i以下のインデックスを持つXのすべての要素が転置されていることに注意してください。これは、正しい要素がX[i]に交換された場合にのみ、各反復が完了するためです。

i > tの場合は常に、インデックスtで以前の交換が行われたことを意味します。tの要素は、上記のように交換され、新しい位置t primeに配置されました。インデックスtが与えられると、次のように行メジャー インデックスtプライムとそれに関連付けられた行番号と列番号を計算できます。

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 に答える