Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| strategies-j [2024/08/29 16:00] – [効率的な魔方陣の数え上げ] mino | strategies-j [2024/08/29 16:14] (current) – [効率的な魔方陣の数え上げ] mino |
|---|
| * 主対角候補を主対角線に並べるために列を入れ替える操作は d<sup>-1</sup>をかけることに対応します。この入れ替えによって、dd<sup>-1</sup> = e と ud<sup>-1</sup> が得られます。eは単位元です。 | * 主対角候補を主対角線に並べるために列を入れ替える操作は d<sup>-1</sup>をかけることに対応します。この入れ替えによって、dd<sup>-1</sup> = e と ud<sup>-1</sup> が得られます。eは単位元です。 |
| * この段階での副対角候補の配置 ud<sup>-1</sup> は、副対角線の配置(逆順置換)と同じ共役類に属する時、そしてその時にのみ、副対角線に変換可能です。N=6の時、この共役類はまさに先に示した図で表される 15の元からなります。 | * この段階での副対角候補の配置 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>とも表現できます。 |
| |
