六面体の頂点をたどる（2）

この問題は、

$p_{s_i,t+1} = \sum_j{q_{s_j \to s_i}p_{s_j,t}}$

という漸化式を解けばよい。
ここで、s_iは状態を表しており、p_{s_i,t}は時刻tに状態s_iを取る確率、q_{s_i→s_j}は状態s_iからs_jに遷移する確率である。
状態とは、すでにたどった点の集合と今の点の位置の組合せである。

状態は数多く存在し、その分漸化式が多く発生することになって計算量が膨大になる。しかし、0から出発するとして、例えば0→1と動いた状態と0→3と動いた状態は回転させただけで同値な状態と言えるだろう。これらの状態をまとめて考えれば漸化式が減って計算が楽になることが期待される。こうして、最後にすべての点をたどった状態s_fに対して、p_{s_f,t}が得られる。

さて、同値な状態とは、適切な回転などすればたどった点今いる点が一致するもの考えればよい（その意味で、これからは正六面体として考えよう）。このような点の移動はどのようなものがあるだろう。

まず、ある点を0に移す。例えば5を0に移すなら、0-4と平行な軸に対して左回りに90℃回転する。そして、その軸に垂直な面に対して対称移動する。そうすると、あとは立体の対角線に回転するか0-3-6-5の面に対して対称移動する。これで8×6＝48個の写像があるはずである。これらの写像を状態に施して、状態が一致すれば同値な状態と言える。まずはこれらの写像を求めよう。写像は配列で表し、例えば、コードにあるrot1は、0が3に移り、1が2に移り、…、という写像を表している。



var rot1 = [ 3, 0, 1, 2, 7, 4, 5, 6 ];

var sym1 = [ 4, 5, 6, 7, 0, 1, 2, 3 ];

var rot2 = [ 0, 4, 5, 1, 3, 7, 6, 2 ];

var sym2 = [ 0, 4, 7, 3, 1, 5, 6, 2 ];

var e    = [ 0, 1, 2, 3, 4, 5, 6, 7 ];
var purm = [ ];     // 求める置換群

for(var i = 0; i < 8; i++) {

    var sigma = e;

    for(var k = 0; k < (i & 3); k++)

        sigma = synthesize(rot1, sigma);

    if(i >> 2)

        sigma = synthesize(sym1, sigma);

    for(var j = 0; j < 6; j++) {

        var sigma2 = sigma;

        for(var k = 0; k < j % 3; k++)

            sigma2 = synthesize(rot2, sigma2);

        if(j >= 3)

            sigma2 = synthesize(sym2, sigma2);

        purm.push(sigma2);

    }

}
for(var i = 0; i < purm.length; i += 2) {

    WScript.Echo("(" + purm[i].join(" ") + ") ("

                            + purm[i+1].join(" ") + ")");

}
function synthesize(a, b) {

    var c = [ ];

    for(var i = 0; i < a.length; i++)

        c[i] = a[b[i]];

    return c;

}

次のように写像が得られた。

(0 1 2 3 4 5 6 7) (0 4 5 1 3 7 6 2)
(0 3 7 4 1 2 6 5) (0 4 7 3 1 5 6 2)
(0 1 5 4 3 2 6 7) (0 3 2 1 4 7 6 5)
(3 0 1 2 7 4 5 6) (1 0 4 5 2 3 7 6)
(4 0 3 7 5 1 2 6) (3 0 4 7 2 1 5 6)
(4 0 1 5 7 3 2 6) (1 0 3 2 5 4 7 6)
(2 3 0 1 6 7 4 5) (5 1 0 4 6 2 3 7)
(7 4 0 3 6 5 1 2) (7 3 0 4 6 2 1 5)
(5 4 0 1 6 7 3 2) (2 1 0 3 6 5 4 7)
(1 2 3 0 5 6 7 4) (4 5 1 0 7 6 2 3)
(3 7 4 0 2 6 5 1) (4 7 3 0 5 6 2 1)
(1 5 4 0 2 6 7 3) (3 2 1 0 7 6 5 4)
(4 5 6 7 0 1 2 3) (3 7 6 2 0 4 5 1)
(1 2 6 5 0 3 7 4) (1 5 6 2 0 4 7 3)
(3 2 6 7 0 1 5 4) (4 7 6 5 0 3 2 1)
(7 4 5 6 3 0 1 2) (2 3 7 6 1 0 4 5)
(5 1 2 6 4 0 3 7) (2 1 5 6 3 0 4 7)
(7 3 2 6 4 0 1 5) (5 4 7 6 1 0 3 2)
(6 7 4 5 2 3 0 1) (6 2 3 7 5 1 0 4)
(6 5 1 2 7 4 0 3) (6 2 1 5 7 3 0 4)
(6 7 3 2 5 4 0 1) (6 5 4 7 2 1 0 3)
(5 6 7 4 1 2 3 0) (7 6 2 3 4 5 1 0)
(2 6 5 1 3 7 4 0) (5 6 2 1 4 7 3 0)
(2 6 7 3 1 5 4 0) (7 6 5 4 3 2 1 0)