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

数学 JavaScript

同値な状態を一意に表すために次のようにしよう。現在の点は0に持ってくるように写像を施す。そのうえで、0を固定した回転・対称変換を施して、状態を表す整数が最も小さくなるものを正規の表現とする。状態を表す整数とは各頂点がすでにたどっていればそのビットを立てたものとここではする。


すなわち、最初の0にある状態は、0のビットを立てて1、次にそこから4に移動した状態は、同値な状態が(0 1),(0 3),(0 4)が考えられるが、状態を表す整数にすると、それぞれ3,9,17だから、3となる。すべてたどった状態は、255となる。


前回得た結果も使って、次のような25個の漸化式が得られた。

p3,n+1 = p1,n + 1/3p3,n
p7,n+1 = 2/3p3,n + 2/3p11,n
p11,n+1 = 1/3p7,n
p15,n+1 = 1/3p7,n + 2/3p15,n
p71,n+1 = 1/3p7,n + 1/3p23,n
p39,n+1 = 1/3p11,n + p27,n
p103,n+1 = 1/3p15,n + 1/3p31,n
p23,n+1 = 1/3p71,n + 1/3p23,n
p47,n+1 = 1/3p71,n + 1/3p23,n + 2/3p79,n + 2/3p31,n
p109,n+1 = 1/3p71,n + 1/3p87,n
p27,n+1 = 1/3p39,n
p79,n+1 = 2/3p39,n + 1/3p47,n
p31,n+1 = 1/3p103,n + 1/3p47,n
p111,n+1 = 2/3p103,n + 1/3p47,n + 1/3p111,n + 2/3p63,n
p63,n+1 = 1/3p109,n + 1/3p111,n + 1/3p63,n + 1/3p61,n
p87,n+1 = 1/3p109,n + 2/3p61,n
p125,n+1 = 1/3p109,n + 2/3p125,n
p231,n+1 = 1/3p79,n + 1/3p95,n
p239,n+1 = 1/3p111,n + 2/3p127,n
p61,n+1 = 1/3p87,n
p175,n+1 = 1/3p87,n + 2/3p95,n
p191,n+1 = 1/3p125,n + 1/3p127,n
p95,n+1 = 1/3p231,n + 2/3p175,n
p127,n+1 = 2/3p231,n + 2/3p239,n + 1/3p175,n + p191,n
p255,n+1 = 1/3p239,n + p255,n

さて、これをどうやって解くのだろう。




var neighbor = [ 1, 3, 4 ];
var purm = [ ];             // 置換群

make_purms();
var q = [ ];                // 遷移確率 * 3

var set_stat = [ ];         // 状態の集合

set_stat[1] = 1;

var queue_stat = [ 1 ];     // 遷移確率計算待ち行列

while(queue_stat.length != 0) {

    var s = queue_stat.shift();

    var set_next = [ ];

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

        var s_next = proceed_stat(s, i);

        increment(q, s, s_next);

        set_next[s_next] = 1;

    }

    

    // 次の状態が現れていなかった状態ならキューに入れる

    for(var s_next in set_next) {

        if(set_stat[s_next] == undefined) {

            set_stat[s_next] = 1;

            queue_stat.push(s_next);

        }

    }

}
for(var s_next in q) {

    var ary_terms = [ ];

    var q_next = q[s_next];

    for(var s in q_next) {

        var n = q_next[s];

        var coeff = n == 3 ? "" : n + "/3";

        ary_terms.push(coeff + "p" + s + ",n");

    }

    WScript.Echo("p" + s_next + ",n+1 = "

                                + ary_terms.join(" + "));

}
// 次の状態を正規化して返す

function proceed_stat(s, i) {

    var pt_next = neighbor[i];

    var next_stat = s | (1 << pt_next); // 置換前の次の状態

    var min_stat = 256;                 // 置換後の次の状態

    for(var k = 0; k < purm.length; k++) {

        // 移動先の点が0に写る置換だけ選ぶ

        if(purm[k][pt_next] == 0) {

            var s_candidate = map(purm[k], next_stat);

            if(s_candidate < min_stat)

                min_stat = s_candidate;

        }

    }

    

    return min_stat;

}
function increment(ary, s, s_next) {

    if(ary[s_next] == undefined)

        ary[s_next] = [ ];

    if(ary[s_next][s] == undefined)

        ary[s_next][s] = 1;

    else

        ary[s_next][s]++;

}
function map(sigma, s) {

    var s_next = 0;

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

        if(s & 1 << i)

            s_next |= 1 << sigma[i];

    }

    return s_next;

}
function make_purms() {

    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 ];

    

    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);

        }

    }

}
function synthesize(a, b) {

    var c = [ ];

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

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

    return c;

}