転置行列への変換が分かりません。

転置行列への変換が分かりません。
現在、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]
が存在しますが、検出できなかったこの流れにどの様な規則性があるのかどうかが分からないままです。
行列を転置行列に一時行列なしで変換する方法と、このアルゴリズムの不完全な部分を教えてください。

＞＜；

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2010/05/08 02:29

まず, 数学的にはほぼ #2 のいう通りです. 添字の変換自体は置換で表現でき, 置換そのものは巡回置換の積で (順序を除いて一意に) 表現できるのですが, 「どのような巡回置換の積になるのか」とか「いくつの巡回置換の積になるのか」というのは簡単ではないと思います. ただ, 「アルゴリズムの出発点が置換連鎖の開始点であるという保証」はあります＞#2... というか, 「どれかの巡回置換に含まれる」ことは簡単.

でじゃあどうするかについてもだいたい #2 に同意. 極端に大きなものでなければ別途作ってしまった方が簡単. 極端に大きいときにはラッパーを作った方がいいと思う.
ただ, こんなの誰もが考えるよなぁと思って検索すると, やっぱり出るんだよな～.

参考URL：http://en.wikipedia.org/wiki/In-place_matrix_tra …

この回答へのお礼

明確な出典にたどり着けました。問題が解決できそうです。ありがとうございました。

お礼日時：2010/05/08 10:56

No.2 回答者： magicalpass 回答日時： 2010/05/08 01:45

　トレースしていけば分かりますが、途中で堂々周りに入ってしまいます。

　例の行列だとたまたま出発点に戻ってきていますが、行列の大きさを変えると永久ループに陥ってしまう場合も多いと思われます。このアルゴリズムでトレース出来るのは、すべての置換が一筆書きのように行われる場合だけです。現実的には置換の連鎖が複数あるばあいもあるだろうし、アルゴリズムの出発点が置換連鎖の開始点であるという保証もありません。

　置換元と置換先が１対１で対応しているのは確かだから、同一メモリ空間上での転置は可能だとは思いますが、置換先を順番にたどればすべての領域を網羅出来るというような単純なものではないのではないでしょうか。よほどメモリに制限のあるマイコンソフトとか、超巨大な行列でも扱わない限り、新たな行列空間を生成するためのメモリをけちるような理由があるとは思えませんが。

この回答へのお礼

剰余による位置の変換があるので単純ではないかもしれませんね。新たなメモリを確保する事に関しては、大きなサイズの行列を扱うので難しいです。

お礼日時：2010/05/08 10:55

No.1 回答者： ICE_FALCON 回答日時： 2010/05/08 01:30

0,7,14,21,28,35,42,49

普通に７の倍数が通っていませんね。
データがたまたま規則的だから解りやすいですね。

この回答へのお礼

そうですね。ただ、Type^(10 * 5)なのにどこから7が出てくるのか良くわかりませんでした。質問のアルゴリズム部分を読んでもらえれば分かると思いますが、目的は一般化する事です。

お礼日時：2010/05/08 10:53