目次
置換を互換の積として表すプログラムを作ってみました。
置換・互換
1, 2, 3, 4, 5 という数字の順番を 1, 4, 2, 5, 3 のような別の順番に入れ替える作業(写像)を置換といいます。 別の言葉で書くと、 集合 ( S ) 上の置換は 全単射 ( f: S rightarrow S ) です。
ここでは有限集合 ( left{ 1, dots , n right} ) での置換を考えます。
書き方
( left{ 1, dots , 5right} ) の置換は次のように表されます。
[ 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) で表すことにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
package com.improve_future.math class Transposition(var a: Int, var b: Int) { init { if (b < a) { val t = a a = b b = t } } override fun toString(): String { return "($a, $b)" } } |
toString() も実装しています。 これにより、 println でわかりやすくアウトプットされます。
置換
置換のクラスを作ります。
Replacement(0, 3, 1, 4, 2) と書いた場合は、
を表すものとします。 番号が 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 |
package com.improve_future.math class Replacement(vararg args: Int) { val numbers: List<Int> = args.toList() val transpositions: List<Transposition> by lazy { val transList = mutableListOf<Transposition>() val p = IntArray(numbers.count()) { 1 } for (i in 0..p.lastIndex) { var n = i while (p[n] == 1) { p[n] = 0 val v = numbers[n] if (v != n && p[v] == 1) { transList.add(0, Transposition(n, v)) n = v } } } transList } val sign: Int by lazy { - transpositions.count() % 2 * 2 + 1 } } |
置換を互換の積に変換するメソッド、符号を計算するメソッドも実装しています。
実行例
|
1 2 3 |
val r = Replacement(0, 3, 1, 4, 2) println(r.transpositions) println(r.sign) |
これは上の例と同じものになります。 次の結果が出力されます。
|
1 2 |
[(2, 4), (3, 4), (1, 3)] -1 |
