Differences

This shows you the differences between two versions of the page.

--- strategies-j [2024/07/27 10:19] – [効率的な魔方陣の数え上げ] mino
+++ strategies-j [2024/08/29 16:14] (current) – [効率的な魔方陣の数え上げ] mino
@@ Line 40: / Line 40: @@
   - 等しい場合
-. と 2. のケースは補数変換にお互いに1対1に対応するため、1. だけ数えて 2倍することで、2.の数え上げを省略することができます。3. の場合は単にそのまま数え上げます。
+. と 2. のケースは補数変換により互いに1対1に対応するため、1. だけ数えて 2倍することで、2.の数え上げを省略することができます。3. の場合は単にそのまま数え上げます。
 . のケースがすべて自己補数的だとは限りません。3.のケースをさらに細かく分解してさらに無駄を省くことができるかも知れません。ただしその分解によるオーバーヘッドが大きくならなければです。
@@ Line 54: / Line 54: @@
       * 答えは「場合による」ですが、対称性の議論を使うとうまい判定法が導けます。副対角線は行と列の入れ替えに対して対称であり、行と列に同じ並べ替えを実行してもこの対称性は決して破れません。従って以下の定理が成り立ちます。
         * 副対角候補は、行と列の交換に対して対称な配置にある時にのみ、副対角線上に整列できる。
-      * 対称な配置が常に副対角線に変換できると単純には言えませんが、小さな Nに対して、副対角要素がとりうる対称的な配置を全て調べることは難しくありません。 N=6のとき、そのような配置は {{ :up-diag2.pdf |この15通り}}だけであり、これらはすべて副対角線に変換可能です。従って、(主対角候補を正しく並べるための列の並べ替えを行った後、)副対角候補の配置が行と列の交換に対して対称であることを確認すれば、M-変換の数だけ魔方陣を見つけたことになります。N=6 における M-変換の自由度は 48です。
+      * 対称な配置が常に副対角線に変換できると単純には言えませんが、小さな Nに対して、副対角要素がとりうる対称的な配置を全て調べることは難しくありません。 N=6のとき、そのような配置は {{ :up-diag2.pdf |この15通り}}だけであり、これらはすべて副対角線に変換可能です。従って、(主対角候補を正しく並べるための列の並べ替えを行った後、)副対角候補の配置が行と列の交換に対して対称であることを確認すれば、[[https://oeis.org/A266237|M-変換]]の数だけ魔方陣を見つけたことになります。N=6 における M-変換の自由度は 48です。
       * 2つ目の節で触れたように、180度の回転による重複は取り除かれるべきです。M-変換の自由度の半分は除去されて24となります。
@@ Line 63: / Line 63: @@
       * 主対角候補を主対角線に並べるために列を入れ替える操作は d<sup>-1</sup>をかけることに対応します。この入れ替えによって、dd<sup>-1</sup> = e と ud<sup>-1</sup> が得られます。eは単位元です。
       * この段階での副対角候補の配置 ud<sup>-1</sup> は、副対角線の配置(逆順置換)と同じ共役類に属する時、そしてその時にのみ、副対角線に変換可能です。N=6の時、この共役類はまさに先に示した図で表される 15の元からなります。
-      * 実際問題として、置換の共役類の判定は置換の巡回置換型で判定します。副対角線の配置は対象全体の並び順を逆にする置換であり、その巡回置換型は floor(N/2)個の2-巡回と(N mod 2)個の1-巡回からなります。我々はすでに主対角候補と副対角候補が N mod 2 個だけの共通項を持つとことを要請済みなため、1-巡回の個数を確認する必要はありません。結果として、確認すべき条件は長さ3以上の巡回がないことであり、( ud<sup>-1</sup> ) <sup>2</sup> = e または ud<sup>-1</sup> = du<sup>-1</sup> = ( ud<sup>-1</sup> )<sup>T</sup>とも表現できます。
+      * 実際問題として、置換の共役類は置換の巡回置換型で判定します。副対角線の配置は対象全体の並び順を逆にする置換であり、その巡回置換型は floor(N/2)個の2-巡回と(N mod 2)個の1-巡回からなります。我々はすでに主対角候補と副対角候補が N mod 2 個だけの共通項を持つとことを要請済みなため、1-巡回の個数を確認する必要はありません。結果として、確認すべき条件は長さ3以上の巡回がないことであり、( ud<sup>-1</sup> ) <sup>2</sup> = e または ud<sup>-1</sup> = du<sup>-1</sup> = ( ud<sup>-1</sup> )<sup>T</sup>とも表現できます。