転置行列への変換が分かりません。
転置行列への変換が分かりません。
現在、type型のrow行column列の行列（row >= 2, column >= 2, row != column）を、要素数がrow * column個ある配列arrayを用いて表現しています。更にR行C列目の要素はrow * C + R番目のarrayの要素で示しています。
そして転置行列ですが、行列type^(row * column)と行列type^(column * row)は要素数が同じなのでarrayと同じサイズの配列を用いて表現が可能ですし、ひとつずつ要素の置換を行えば新しく一時的にtype^(column * row)の行列を作って単純に代入処理をするよりもメモリに負担が掛からないはずです。
よって今は以下のアルゴリズムを考案し実装したのですが、問題が発生しました。
（以下配列i番目の要素をarray[i - 1]、行列matrixのa行b列の要素はmatrix[a - 1][b - 1]と記す。）
----
入力 matrix in type^(row * column)とresult_matrix in type^(column * row)を示す、row * column個の要素を持つarrayが与えられる。
手順1 変数xに1を、変数yに0を代入する。一時要素領域tmp_elemにmatrix[x][y] = array[x + y * row]を代入する。
手順2 result_matrix[y][x] = array[y + x * column]とtmp_elemを交換する。
手順3 変数tにy + x * columnを代入し、xにtとrowの剰余を、yにtをrowで割った値の整数部を代入する。
手順4 xが1でかつyが0なら終了。そうでなければ手順2から再度処理を実行。
----
分かりやすく書くと、与えられた始点の位置にある転置前の行列としての要素を取得し、次に行列を既に転置された形のものとみなしてから、さっき取得した要素を転置後にあるべき場所へと移動させ、そこに元々あった要素に対して更に再帰的に手順を適応する感じです（実装ではループに落としていますが）。終了条件は「交換対象が始点へ戻ってきたとき」です。
しかし、次々と交換していく流れにおいて処理されない要素が出てきました。integer^(10 * 5)における以下の行列
----
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
----
の転置（仮）
----
0, 10, 20, 30, 40,
1, 11, 7, 31, 41,
2, 12, 22, 32, 14,
3, 13, 23, 33, 43,
4, 21, 24, 34, 44,
5, 15, 25, 28, 45,
6, 16, 26, 36, 46,
35, 17, 27, 37, 47,
8, 18, 42, 38, 48,
9, 19, 29, 39, 49,
----
です。
ここではメインの流れmatirx[1][0] -> ... -> matrix[0][1]では走査できない要素の流れとして
matrix[5][3] -> matrix[8][2] -> matrix[2][4] -> matrix[4][1] -> matrix[1][2] -> matrix[7][0]
が存在しますが、検出できなかったこの流れにどの様な規則性があるのかどうかが分からないままです。
行列を転置行列に一時行列なしで変換する方法と、このアルゴリズムの不完全な部分を教えてください。
＞＜；
お礼
返信遅れてすみません。 詳しい解説ありがとうございます。