おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です

Githubにsymmetric_groupをアップロード

2/26追記

本日、プログラムを書き直してレポジトリにアップロードしました。demo.rbも書き換えられていて、下にあるプログラムは新バージョンでは動きません。レポジトリに含まれているdemo.rbを使ってください。変更の主な理由は置換の積の速度をあげることです。元バージョンでは置換の積をその定義どおりに計算しており、計算量が多くなっています。それを新バージョンでは、置換を順に並べ、そのインデックスで置換を表し、インデックスの2次元配列の乗算表を用いることにより、格段に積の計算速度を上げています。これで、5次対称群のすべての部分群を求めるのに、1時間10分=>1分20秒に短縮されました。最初のアルゴリズムが悪すぎ。(追記以上)。

GithubにSymmetric_groupというプログラムをアップロードしました。このプログラムはRubyで書かれています。n次対称群(これは置換群と言った方が分かりやすいかもしれません)を計算をしたり、生成部分群を求めたりするプログラムです。

置換群の積の計算は、いくつかの数をたどりながら行うので面倒です。それをコンピューターにやらせれば楽になるのではないかと思い、プログラムを作りました。また、このプログラムは単に掛け算をサポートするだけではなく、群の生成をサポートします。例えば4次の対称群において、2つの要素から部分群を生成したいとします。この部分群は2つの要素を含むような最小の部分群です。与えられた2つの置換から始め、その積や逆元を繰り返し計算します。そしてすでに出てきた要素は捨て、新しい要素は追加し、これ以上新しい要素が出なくなったら、それらの要素の全体が部分群になります。手作業でやるのは、少し大きな部分群では面倒であり、場合によっては事実上不可能です。それをコンピューターで計算すれば楽だし、実用的だと思いました。

プログラムのPGroupクラスのインスタンス生成(initializeメソッド)でこの計算をしていますが、非常にシンプルです。このとき有限集合Aが、AA = Aならば、Aは部分群になるという定理を使っています。

例えば二面体群D4は、(1234)の巡回群と(13)の互換をもとに生成します。これをプログラムで計算すると瞬時に行ってくれます。人間の計算でもそんなに大変ではなのですが、プログラムしたほうがずっと早く答えを見つけられます。また、(1234)の巡回群と(12)の互換で群を生成すると、4次対称群全体になります。これもコンピューターで計算するとあっという間に分かります。demo.rbがそのプログラムで、実行すると次のようなメッセージが出ます。

D4 is a dihedral group. D4 includes rotations and refletions of a square.
It is expressed with a permutation of vertices and it is generated from
two cycles [1,2,3,4] and [1,3],
Let s be [1,2,3,4] and t be [1,3].
They are created with Permutation.new([2,3,4,1]) and
Permutation.new([3,2,1,4]) respectively.

st = PSet.new (s,t)
D4 = PGroup.new (st)

D4 = [[1,2,3,4],[1,3],[1,3][2,4],[1,4][2,3],[1,2][3,4],id,[1,4,3,2],[2,4]]


If you generate a group from [1,2,3,4] and [1,2] instead of the cycles above,
the symmetric group S4 will be generated.
s = Permutation.new([2,3,4,1])
t = Permutation.new([2,1,3,4])
st = PSet.new (s,t)
S4 = PGroup.new (st)

S4 = [[1,2,3,4],[1,2],[1,3][2,4],[1,3,4],[2,3,4],id,[1,4,3,2],[1,4,2,3],
[1,2,4,3],[1,3,2,4],[1,3,4,2],[2,4,3],[1,3,2],[1,4,2],[1,4,3],[1,4][2,3],
[1,4],[3,4],[2,3],[2,4],[1,3],[1,2,3],[1,2,4],[1,2][3,4]]

置換群は、群論の本では例題として良く取り上げられ、面倒な計算が練習問題に良く出されていました。学習者は、その計算を手作業で時間をかけて行っていたのですが、このプログラムを使うと時間短縮になり、よりスムーズに群の学習が進むと思います。