Kotlin: 置換を互換の積にする


置換を互換の積として表すプログラムを作ってみました。

置換・互換

1, 2, 3, 4, 5 という数字の順番を 1, 4, 2, 5, 3 のような別の順番に入れ替える作業(写像)を置換といいます。 別の言葉で書くと、 集合 \( S \) 上の置換は 全単射 \( f: S \rightarrow S \) です。

ここでは有限集合 \( \left\{ 1, \dots , n \right\} \) での置換を考えます。

書き方

\( \left\{ 1, \dots , 5\right\} \) の置換は次のように表されます。

\[ \sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 & 5 & 3
\end{pmatrix} \]

これは最初の例のように、 1, 2, 3, 4, 5 を 1, 4, 2, 5, 3 に入れ替える置換を表します。

互換とは、置換の中でも2つの要素だけを入れ替える写像です。 3, 4 を入れ替える互換は、 置換の形でも記述できますが、 次のように書くこともできます。

\[ \begin{pmatrix} 3 & 4 \end{pmatrix} \]

任意の置換は互換の積で表すことができます。(どのような置換も、2つの要素を順に入れ替えていくことで実現できます。)

\begin{eqnarray} & & \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 & 5 & 3
\end{pmatrix} \\
& = & \begin{pmatrix} 3 & 5 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix} \begin{pmatrix} 2 & 4 \end{pmatrix} \end{eqnarray}

積の形で書かれた互換は、右のものから順に作用していきます。 互換は写像ですから、右から順に適用されると考えます。

偶数個の互換の積で表される置換を偶置換、奇数個の互換の積で表される置換を奇置換といいます。 置換には符号が定義されており、 偶置換では 1、 奇置換では -1 です。

コード

置換を互換の積に変換するコードを書いてみます。 ついでに置換の符号も計算できるようにします。

互換

互換を表すクラスを作ります。

互換 \( (1, 2) \) を Transposition(1, 2) で表すことにします。

toString() も実装しています。 これにより、 println でわかりやすくアウトプットされます。

置換

置換のクラスを作ります。

Replacement(0, 3, 1, 4, 2) と書いた場合は、

\[ \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 & 5 & 3
\end{pmatrix} \]

を表すものとします。 番号が 0 から始まることに注意してください。 上段は最初から決まっていますので、下段のみ表す形にしています。

置換を互換の積に変換するメソッド、符号を計算するメソッドも実装しています。

実行例

これは上の例と同じものになります。 次の結果が出力されます。