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

Table of Contents

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

置換・互換

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) で表すことにします。

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)"
}
}

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) と書いた場合は、

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

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

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
}
}

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

}

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

実行例

val r = Replacement(0, 3, 1, 4, 2)
println(r.transpositions)
println(r.sign)

val r = Replacement(0, 3, 1, 4, 2)

println(r.transpositions)

println(r.sign)

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

[(2, 4), (3, 4), (1, 3)]
-1

1 2	[(2, 4), (3, 4), (1, 3)] -1

The Life

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

置換・互換

書き方

コード

互換

置換

実行例

関連記事

この記事を見た人は次の記事も見ています

A Life Summary of an Gypsy