おもこん

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

Symmetric_group レポジトリを更新

対称群の部分群を求めるプログラム(symmetric group)をCで書き直しました。Ruby ではなかなか速度が上がらないので、Cに書き直せば速度が上がると期待したのです。ところが、実際にはさして速度が上がりませんでした。5次対称群の部分群を求めるプログラムでは、最初の段階でRubyが80秒、Cが60秒ぐらいでした。よく調べてみると無駄な箇所があったので、RubyもCも書き換えたところ、Rubyが1分を切り(56秒)、Cは40秒で答えが出るようになりました。

しかしまだ満足はしていません。インターネットで対称群の部分群を求めるプログラムを探してみましたが、アルゴリズムを解説しているようなものは見つかりませんでした。おそらく、さほど新しい問題ではないので、すでに誰かが良いアルゴリズムを見つけているのではないかと思います。特に有限群の研究者にとっては、コンピューターがかなり威力を発揮すると思うので、すでにこの問題の有力なアルゴリズムが既知のものになっているのではないでしょうか。

今日、Githubのリポジトリを更新しました。興味のある人はここを見て下さい。また。良いアルゴリズムをご存知の方がいたら教えていただければ助かります。最後に4次対称群と5次対称群の部分群の個数について記しておきます。

  • 4次対称群 => 30個
  • 5次対称群 => 156個