検証的プログラミング(1) - エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで、数式で表すのが難しいものに関する証明をやろうとしていたのですが、Blocklyを使って行おうとするとブロックを組み合わせるときに選択することは難しいということがわかりました。そこで、プログラム検証のようにプログラムを書いた後で、数式で表すことが難しい部分だけをビジュアルプログラミングで行うことはできないかということを考えていきます。うまくできるかどうかはわかりませんがこれをここでは検証的プログラミングと呼ぶことにします。

置換のパリティー(1)

この例として置換のパリティーについて考えます。有限集合 $\{1,2,\cdots,n\}$ の自分自身への全単射を置換(permutation)と呼びます。置換の全体を $S_n$ と書きます。2つの要素を入れ替えるだけの置換を互換(transposition)と呼びます。 $i$ と $j$ を入れ替える互換を $(i,j)$ と書きます。または合成の方向を逆方向にして、置換 $\sigma$ に対して、 $\sigma(i)$ と $\sigma(j)$ を入れ替える互換を $(i,j)$ と書きます。隣り合う2つの要素を入れ替えるだけの互換を基本互換(fundamental transposition)または隣接互換(adjacent transpositions)と呼びます。任意の置換はいくつかの互換の合成で表すことができます。そのように表したとき、合成する互換の個数が偶数であるか奇数であるかは表し方に依存しません。これを置換の偶奇性(parity)と呼びます。この個数が偶数のとき偶置換(even permutation)、奇数のとき奇置換(odd permutation)と呼びます(Wikipediaによる)。

置換 $\sigma$ に対して、 $i < j$ かつ $\sigma(i) > \sigma(j)$ であるような $i, j$ の組 $(i,j)$ を転倒(inversion)と呼びます。転倒の個数を転倒数と呼びます。 $\sigma$ と基本互換 $(i,j)$ を合成すると、組 $(i,j)$ が転倒ならば転倒数は $1$ 減少し、組 $(i,j)$ が転倒でなければ転倒数は $1$ 増加します。バブルソート(ここではバブルソートは隣り合う2つの要素を入れ替えることを繰り返すものとします)によって $\sigma$ をいくつかの基本互換の合成で表すことができます(Wikipediaによる)。

以下のことを示します。

任意の置換と任意の基本互換を合成すると、基本互換の組が転倒であるかどうかによって転倒数は減少または増加します。
任意の置換はバブルソートによっていくつかの基本互換の合成で表すことができます。ここではこの基本互換の個数のパリティー(偶数か奇数か)を置換のバブルソートのパリティーと呼ぶことにします。バブルソートは最初の隣接する転倒を入れ替えることを繰り返すものとします。
任意の置換と任意の基本互換を合成すると、元の置換のバブルソートのパリティーと合成後のバブルソートのパリティーは異なります。
任意の互換のバブルソートのパリティーは $1$ (奇数)となります。
いくつかの互換の合成のバブルソートのパリティーは、互換の個数のパリティー(偶数か奇数か)と一致します。
置換をいくつかの互換の合成として何通りかで表したとき、それらの互換の個数のパリティー(偶数か奇数か)はすべて一致します。

以上のような方針で「ビジュアルプログラミング」の「偶置換・奇置換」の項目の内容をTypeScriptで書いていきます。

『群論日評ベーシック・シリーズ』、『代数学入門---先につながる群，環，体の理論NBS 日評ベーシック・シリーズ』などでは置換を互換の合成に分解することによって偶置換、奇置換を定義しています。バブルソートによる定義の方が簡単だとは思うのですが、バブルソートのアルゴリズムの記述は数学の本にはなじまないということでこのような定義になっているものと思われます。