数を並びかえる(3)

追記　まとめて移転先で記事にしました：Clojure を学ぶ

参考文献 : プログラミング Clojure 第2版、(Stuart Halloway and Aaron Bedra 著、川合史朗訳、オーム社)

\(S_{3}\) だけではつまらないのでいくつか定義しておく :

(def S4 (symmetric-group 4))

(def A4 (make-fns (filter even-permutation? (permutation [1 2 3 4]))))

(def A3 (make-fns (filter even-permutation? (permutation [1 2 3]))))

前回で必要なものは揃ったのでいくつか計算例をやってみる。

共役 :

(defn conjugate [x y] ; y x y^{-1}
  (product y x (inverse y)))

軌道 :

(defn orbit [x G]
  (set (as-permutation (map #(conjugate x %) G))))

この定義は良くない。本当は #function のリストを返すほうが良いし、共役以外の軌道もあるので関数を渡せるようにしたほうが良いが、ここではこれで済ませることにする。

試してみる :

(for [g S3] (orbit g S3))
=>
(#{[1 2 3]} 
 #{[1 3 2] [2 1 3] [3 2 1]} 
 #{[1 3 2] [2 1 3] [3 2 1]} 
 #{[2 3 1] [3 1 2]}
 #{[2 3 1] [3 1 2]}
 #{[1 3 2] [2 1 3] [3 2 1]})

重複があるがきれいに分解される。重複をとりのぞけば共役類分解が得られる:

(defn classify [G]
  (set (for [x G] (orbit x G))))

使ってみる :

(classify S3)
=>
#{#{[1 2 3]} 
  #{[2 3 1] [3 1 2]} 
  #{[1 3 2] [2 1 3] [3 2 1]}}

(classify S4)
=>
#{#{[4 3 2 1] [2 1 4 3] [3 4 1 2]} 
  #{[1 4 3 2] [1 3 2 4] [2 1 3 4] [3 2 1 4] [1 2 4 3] [4 2 3 1]} 
  #{[1 2 3 4]} 
  #{[2 3 4 1] [2 4 1 3] [4 1 2 3] [3 1 4 2] [4 3 1 2] [3 4 2 1]} 
  #{[1 3 4 2] [1 4 2 3] [4 1 3 2] [3 1 2 4] [4 2 1 3] [2 4 3 1] [3 2 4 1] [2 3 1 4]}}

ちょっと長くなるが \(S_{5}\) の分解も計算してみる。とても手で計算する気は起きないがわけなくやってくれる :

(classify (symmetric-group 5))
=>
#{#{[5 1 4 3 2] [3 4 5 2 1] [4 5 2 1 3] [3 5 1 2 4] [2 4 5 1 3] [4 1 5 2 3] [2 5 4 3 1] [4 3 2 5 1] [3 5 4 1 2] [2 1 5 3 4] [5 3 4 2 1] [2 3 1 5 4] [3 4 1 5 2] [3 1 2 5 4] [5 4 1 2 3] [5 3 2 1 4] [4 5 1 3 2] [2 1 4 5 3] [5 4 2 3 1] [4 3 5 1 2]} 
  #{[3 2 5 1 4] [2 3 4 1 5] [5 1 2 4 3] [4 3 1 2 5] [4 2 5 3 1] [1 4 2 5 3] [4 1 3 5 2] [3 1 4 2 5] [2 4 3 5 1] [1 5 4 2 3] [5 2 4 1 3] [2 4 1 3 5] [3 5 2 4 1] [1 5 2 3 4] [3 2 4 5 1] [5 3 1 4 2] [3 4 2 1 5] [3 1 5 4 2] [1 3 4 5 2] [5 2 1 3 4] [2 5 3 1 4] [2 5 1 4 3] [5 1 3 2 4] [2 3 5 4 1] [4 5 3 2 1] [1 3 5 2 4] [1 4 5 3 2] [4 2 1 5 3] [4 1 2 3 5] [5 4 3 1 2]} 
  #{[2 1 3 4 5] [4 2 3 1 5] [1 5 3 4 2] [1 2 5 4 3] [1 4 3 2 5] [1 3 2 4 5] [3 2 1 4 5] [5 2 3 4 1] [1 2 3 5 4] [1 2 4 3 5]} 
  #{[1 3 5 4 2] [1 3 4 2 5] [1 5 2 4 3] [5 1 3 4 2] [3 2 4 1 5] [5 2 1 4 3] [4 2 1 3 5] [3 1 2 4 5] [4 2 3 5 1] [1 4 2 3 5] [3 2 5 4 1] [2 4 3 1 5] [2 3 1 4 5] [5 2 3 1 4] [1 2 5 3 4] [1 5 3 2 4] [1 4 3 5 2] [2 5 3 4 1] [4 1 3 2 5] [1 2 4 5 3]} 
  #{[1 2 3 4 5]} 
  #{[4 2 5 1 3] [5 4 3 2 1] [2 1 3 5 4] [2 1 4 3 5] [4 5 3 1 2] [1 3 2 5 4] [4 3 2 1 5] [3 5 1 4 2] [1 4 5 2 3] [5 2 4 3 1] [5 3 2 4 1] [3 2 1 5 4] [1 5 4 3 2] [3 4 1 2 5] [2 1 5 4 3]} 
  #{[2 4 5 3 1] [2 5 1 3 4] [5 3 1 2 4] [4 1 2 5 3] [4 5 2 3 1] [2 3 4 5 1] [4 5 1 2 3] [3 5 2 1 4] [3 1 5 2 4] [4 3 1 5 2] [5 4 2 1 3] [5 1 4 2 3] [5 3 4 1 2] [3 4 5 1 2] [5 4 1 3 2] [3 5 4 2 1] [3 1 4 5 2] [2 5 4 1 3] [2 3 5 1 4] [4 1 5 3 2] [2 4 1 5 3] [4 3 5 2 1] [5 1 2 3 4] [3 4 2 5 1]}}

次に \(D(G) := \{xyx^{-1}y^{-1} | x,y \in G\}\)

(defn D [G]
  (for [x G y G] (product x y (inverse x) (inverse y))))

について\(D(S_n)=A_{n}\)を示したい。普通にやると n=4 の場合が面倒だがあっさりできてしまう。

(sg= A3 (D S3))
=>
true

(sg= A4 (D S4))
=>
true

普通に(？)やるには上の\(S_{4}\)の分解を使うのが一つの方法だが、そもそも手計算で分解するのが面倒だから随分楽にはなる。n>=5 の場合は教科書にのっていると思う。

もう少しやろうと思ったが clojure の勉強という意味では面白くなくなってしまったのでここまでとする。