読者です 読者をやめる 読者になる 読者になる

有限群の実装(Ruby)

Ruby 数学

クラス Group の set は定義された集合(標準添付ライブラリの Set クラスを使う)、&op は定義された演算(Proc オブジェクト)。@ie単位元、@order は位数、インスタンスメソッド inverse(a) は a の逆元を与えます。(結合法則の確認はひどく時間がかかる場合があるので、スキップを選択できます。)

# encoding: Shift_JIS
require 'set'

class Group
  def initialize(set, cck=true, &op)
    @set = set; @op = op
    @order = @set.size    #位数
    if @set.class != Set then raise "Set クラスを使ってください" end
    unless @op.arity == 2 then raise "演算の引数の数は2でなければなりません" end
    @set.each do |x|
      @set.each do |y|
        unless @set.include?(@op[x, y]) then raise "群が閉じていません" end
      end
    end
    if cck
      @set.each do |x|
        @set.each do |y|
          @set.each do |z|
            unless @op[@op[x, y], z] == @op[x, @op[y, z]]
              raise "演算の結合法則が成立していません"
            end
          end
        end
      end
    end
    @ie = nil
    @set.each do |a|
      if ie?(a)
        @ie = a
        break
      end
    end
    unless @ie then raise "単位元が存在しません" end
    @set.each do |a|
      unless @set.include?(inverse(a)) then raise "逆元が存在しません" end
    end
  end
  attr_reader :ie, :order
  
  def inverse(a)
    @set.each do |x|
      if @op[a, x] == @ie and @op[x, a] == @ie then return x end
    end
    raise "逆元が存在しません"
  end
  
  def ie?(a)
    @set.each do |x|
      unless x == @op[a, x] and x == @op[x, a] then return false end 
    end
    true
  end
end

3次の対称群(参照)を実装してみました。

perm3 = lambda do |num1, num2|
  h = {}; a = ""
  for i in 0..2
    h[i] = num1[i].to_i
  end
  for i in 0..2
    a[i] = h[num2[i].to_i].to_s
  end
  a
end


ar = ["012", "021", "102", "120", "201", "210"]
s = Set.new(ar)
g = Group.new(s, &perm3)

p g.ie                #=>"012"  単位元
p g.inverse("120")    #=>"201"  逆元
ar.each {|x| print x, "", g.inverse(x), ", "}
#=>012→012, 021→021, 102→102, 120→201, 201→120, 210→210,  すべての逆元

4次の対称群もまったく同様です。

perm4 = lambda do |num1, num2|
  h = {}; a = ""
  for i in 0..3
    h[i] = num1[i].to_i
  end
  for i in 0..3
    a[i] = h[num2[i].to_i].to_s
  end
  a
end


ar = [0, 1, 2, 3].permutation(4).map(&:join)
s = Set.new(ar)
g = Group.new(s, &perm4)

p g.ie                 #=>"0123"  単位元
p g.order              #=>24      位数
p g.inverse("1203")    #=>"2013"  逆元
ar.each {|x| print x, "", g.inverse(x), ", "}
#0123→0123, 0132→0132, 0213→0213, 0231→0312, 0312→0231, 0321→0321, 1023→1023,
#1032→1032, 1203→2013, 1230→3012, 1302→2031, 1320→3021, 2013→1203, 2031→1302,
#2103→2103, 2130→3102, 2301→2301, 2310→3201, 3012→1230, 3021→1320, 3102→2130,
#3120→3120, 3201→2310, 3210→3210,   すべての逆元

クラインの4元群。

ar = %w(e a b c)
op = lambda do |x, y|
  if x == "e" then re = y
  elsif y == "e" then re = x
  elsif (x == "a" and y == "b") or (x == "b" and y == "a") then re = "c"
  elsif (x == "b" and y == "c") or (x == "c" and y == "b") then re = "a"
  elsif (x == "c" and y == "a") or (x == "a" and y == "c") then re = "b"
  else re = "e" end
  re 
end


g = Group.new(Set.new(ar), &op)
p g.ie    #=>"e"    単位元
ar.each {|x| print x, "", g.inverse(x), ", "}   #=>e→e, a→a, b→b, c→c,  すべての逆元

ar.each do |x|
  ar.each do |y|
    print "(#{x}, #{y})→#{op[x,y]}, "
  end
end
#(e, e)→e, (e, a)→a, (e, b)→b, (e, c)→c, (a, e)→a, (a, a)→e, (a, b)→c,
#(a, c)→b, (b, e)→b, (b, a)→c, (b, b)→e, (b, c)→a, (c, e)→c, (c, a)→b,
#(c, b)→a, (c, c)→e,

いい加減に群を定義するとエラーが出る。これは演算については閉じているが、単位元がない。
その他、色々と集合と演算を定義して、群になるか遊んでみて下さい。

ar = %w(a b)
op = lambda {|x, y| x}
g = Group.new(Set.new(ar), &op)   #=>**.rb:**:in `initialize': 単位元が存在しません (RuntimeError)