Let's write β

プログラミング中にできたことか、思ったこととか

ルービックキューブと置換とHaskell

何度かプログラムを書いてるので、自分のためのまとめ記事(自分への記事なのでけっこうはしょっています)

ルービックキューブの各セルの面に番号をわりあてる

ルービックキューブの表面には全部で 9x6 = 54個のセルの表面が見えています。
この面の事をセル面とここでは呼びます。
セル面は初期配置(6面すべてそろった状態)の状態で番号を現在の色をわりあてます。
たとえば (0, White),(1, White)..(9, Orange)..のようにわりあてます。この番号の振りかたは対応づいていればかまわないので任意です

ルービックの回転

この状態でルービックキューブ自体の向きを変化させずに、回転の動作を実行すると、セル面の配置とキューブ自体との位置関係が変化します。しかし、ここではその位置関係を無視してセルにわりあてられている番号が変化したのだと捉えます。たとえばセルの番号が1から18に変化した等と考えます。
番号を変化させるとキューブ全体の色の配置もかわってきますのでこの変化は色のほうを変化させた事と等価です。

回転と置換

さて、キューブへの操作を番号の変化と考えるとしましたが、これは数学では置換という物によって表現できます(英語ではPermutation)。置換は数字をどの数字に変化させるかという演算を表現したものです。このようにする事でキューブの回転を数学上で捉える事ができます。

置換の積

置換と置換は合成する事ができます。置換A,Bが存在するときaがAによってbに移されbがBによってcに移されるのならば合成置換 A . Bによってaはcに移されます。

またここでは便宜のためにAにふくまれるがBにふくまれない置き換え、とBにふくまれるがAにふくまれない置き換えも A . B にふくまれる事にします。

置換と巡回置換

キューブの操作を置換で表現する事にしましたが、この置換について証明されている定理があります。それは


任意の置換は巡回置換の積に分解できる

という事です。巡回置換とは何回かくりかえすと元の状態にもどる置換の事で、それ以外の数字を移さない物です。まぁ簡単にいくとaをbに移すならばbもその置換の中でどこかに移されているような物です。(aをbにうつすのにbはどこでもあつかわれない、という事はないという事です)
一つの置換はこのような巡回置換の積に分解できる事が証明されています。

巡回置換の周期

巡回置換は閉じているので、何度か置換させていくともとに戻ります。これを巡回置換の周期と呼ぶ事にします。

置換の周期

置換はいくつかの巡回置換に分解できる事をいい、また巡回置換は周期をもつ事をいいました。
ここから置換の周期を求められます。置換を構成する巡回置換の周期の最小公倍数がそれです。

ルービックキューブの操作の周期

ルービックキューブの操作は置換でとらえられる事をいいました、置換には周期があたえられる事もいいました。よってルービックキューブの操作にも周期がある事がいえます。
またルービックキューブの連続した操作を置換の積だと考えるとルービックキューブのまとまった操作の周期をもとめる事ができます。

Haskellで実装

上でいっていた事をHaskellで実装しました。
rubik-cube-hs

たとえば、操作R'とD'のペアを何度くりかえすと元の状態にもどるのでしょうか

let action = P.inverse R.turnR mappend P.inverse R.turnD
-- Calc cycle length of action.
foldl1 lcm (map (\x -> P.cycleLength x) $ P.findCycles action)
=> 105

求めた答は105回だそうです。
僕は自宅で実際にためしてみました、無事105回で完全に元にもどりました。
他の操作についても計算してみるとおもしろそうですね。