１．運を天に任せる
新しい学年が始まると必ず委員の選出が行われる。大抵、誰もなりたがらないものだから、運を天に任せてあみだくじで行うことになる。このあみだくじ、どのような構造をしているのだろうか。
学期初めに行われるあみだくじは、縦線に横棒を入れ、順番が相互に入れ替わるようにして、上に書かれた名前の人が、下に書かれている委員名のどれに当たるかを競うお楽しみ（？）といっていいだろう。
通常、あみだくじは上に書かれているもの(先の説明では人の名前)と下に書かれているもの(先の説明では委員名)とが異なることが多いが、ここでは、上も下も同じ席順とし、あみだくじは席順の入れ替えを決めるものと考える。
問題を具体的にするために、人はa,b,cの三人いるものとし、その席順はカッコでくくって表すこととする。例えば、(a,b,c)のように表す。この場合、aが左で、bが真ん中で、cが右ということにする。席順の入れ替えは6通りあるので、あみだくじも下図のように6通り存在する。
あみだくじは、横線の引き方は様々あるが、上の6種類と異なった引き方であっても、機能としては上の6通りのどれかと等価である。
席順も同じように6通りである。即ち、(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)の6通りである。
現在の席順に、あみだくじを施すと新しい席順が得られる。例えば、左から2番目のあみだくじを施したとすると下図のような席順が得られる。
上の図は、現在の席順が(a,b,c)であればこのあみだくじを施した後の席順は(a,c,b)であるといっている。
なお、最も左にあるあみだくじは次の席順は現在の席順と同じである。さて、あみだくじの構造を圏論の言葉で置き換えてみよう。
席順の集まり、即ち、(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)は圏論では対象と呼ばれる。例えば、\(A={(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}\)と表すことができ、\(A\)が対象で、\( (a,b,c) \)などはその要素である。
あみだくじの一つ一つは圏論では射と呼べれる。従って、\(p_0,p_1,p_2,p_3,p_4,p_5\)はそれぞれ射で、\(p_i : A \rightarrow A\)である。但し、\(i \in [0,5] \)である。
射の合成は、あみだくじを連続して施すことで実現される。即ち、\(p_j \circ p_i (x) = p_j (p_i (x)) \)、ここで、\(i,j \in [0,5] \)、\(x \in A \)である。
２．Haskellであみだくじを実現する
Haskellであみだくじを実現すると次のようになる。
module Permutation where data Person = A | B | C deriving (Eq, Ord, Show, Read, Bounded, Enum) data Seat = Seat {left :: Person, middle :: Person, right :: Person} deriving (Eq, Show) p0 :: Seat -> Seat p0 x = x p1 :: Seat -> Seat p1 x = Seat {left = left x, middle = right x, right = middle x} p2 :: Seat -> Seat p2 x = Seat {left = middle x, middle = left x, right = right x} p3 :: Seat -> Seat p3 x = Seat {left = middle x, middle = right x, right = left x} p4 :: Seat -> Seat p4 x = Seat {left = right x, middle = left x, right = middle x} p5 :: Seat -> Seat p5 x = Seat {left = right x, middle = middle x, right = left x}
上記のプログラムで、人と席順はPersonとSeatという新しいデータ型として定義されている。特に、Seatはレコード構文を用いて定義されている。
あみだくじは関数p0,p1,p2,p3,p4,p5として定義されている。
これを使ってみる。
*Permutation> let seat = Seat {left = A, middle = B, right = C} *Permutation> p0 seat Seat {left = A, middle = B, right = C} *Permutation> p1 seat Seat {left = A, middle = C, right = B} *Permutation> p3 seat Seat {left = B, middle = C, right = A} *Permutation> (p4.p3) seat Seat {left = A, middle = B, right = C} *Permutation> (p5.p4.p3.p2) seat Seat {left = C, middle = A, right = B}
上の例で、最初にseatという席順を用意し、これにいろいろなあみだくじを施してある。特に、下の二つは、あみだくじの合成を行ったものである。
次にあるあみだくじで席順を変えたときに、その席順を元の席順に戻すあみだくじがどれであるかを求めることにする。即ち、それぞれのあみだくじに対してその逆のあみだくじを求めることにする。そのプログラムをHaskellで記述すると次のようになる。
original = Seat {left = A, middle = B, right = C} inverse :: (Seat -> Seat) -> String inverse f | left s0 == A && middle s0 == B && right s0 == C = "function p0" | left s1 == A && middle s1 == B && right s1 == C = "function p1" | left s2 == A && middle s2 == B && right s2 == C = "function p2" | left s3 == A && middle s3 == B && right s3 == C = "function p3" | left s4 == A && middle s4 == B && right s4 == C = "function p4" | left s5 == A && middle s5 == B && right s5 == C = "function p5" | otherwise = "no function p" where s0 = (p0 . f) original s1 = (p1 . f) original s2 = (p2 . f) original s3 = (p3 . f) original s4 = (p4 . f) original s5 = (p5 . f) original
上記のプログラムは次のようになっている。適当な席順(プログラムではoriginal）を決めて、与えられたあみだくじfに対して、席順を元に戻す、即ち、最初の席順にするあみだくじを探せばよいので、すべてのあみだくじの中からそのようなものを探すことになる。
それではプログラムを実行してみる。
*Permutation> inverse p0 "function p0" *Permutation> inverse p1 "function p1" *Permutation> inverse p2 "function p2" *Permutation> inverse p3 "function p4" *Permutation> inverse p4 "function p3" *Permutation> inverse p5 "function p5"
驚いたことに、p3とp4を除いて、すべてのあみだくじが自分自身が元に戻すあみだくじになっている。p3とp4は、入れ替わって元のあみだくじになっている。あみだくじでの操作が元に戻せるというのは面白い現象ではあるが、少し単純すぎて楽しくないような気がする。
