[javascript]structure of hanoi

readme.ja.md

ハノイの塔の構造について考える

「ハノイの塔」を解く手順は、再帰関数でかくと以下のようになる:

function hanoi(saucer, from, to, rest) {
    if (saucer === 0) return;
    hanoi(saucer - 1, from, rest, to);
    console.log(`move ${saucer} from ${from} to ${to}`);
    hanoi(saucer - 1, rest, to, from);
}

hanoi(3, "A", "B", "C");

普通はこれを分割統治の例として手続き的な側面でしかみないが、 今回はこのような再帰関数の背後に存在している 再帰構造を明らかにしてみる。

最初の引数だけに注目すると、この再帰構造は深さsaucerの 完全二分木の走査と一緒である。

---

コードを以下のように変え、(手順の出力ではなく)木構造をつくる:

function hanoi(saucer, from, to, rest) {
    if (saucer === 0) return undefined;
    const left = hanoi(saucer - 1, from, rest, to);
    const center = `${from}->${to}`;
    const right = hanoi(saucer - 1, rest, to, from);
    return [left, center, right].filter(e => e);
}

console.log(hanoi(3, "A", "B", "C"));

このコードの結果は、 [[["A->B"], "A->C". [B->C"]], "A->B", [[C->A"], "C->B", ["A->B"]]] となる。

この結果の完全二分木には、左からの順が実行順、木の深さnが動かす皿(4-n)、 要素の文字列が移動先、となっていて、手順に関するすべての情報を含んでいる。 そして、手順数は全部で、(2^n - 1)回になる。

つまりは、ハノイの塔の解の構造は、皿の数を深さとする、完全二分木である。

---

次にこの結果を、皿ごとにピックアップしてみる:

• 皿1: ["A->B", "B->C", "C->A", "A->B"]
• 皿2: ["A->C", "C->B"]
• 皿3: ["A->B"]

あたり前のことだが、すべての皿でAで始まりBで終わり、 かつ次の移動元は前の移動先であり、 そしてA,B,Cは均等に出てくる(A->B->C-A->...、もしくは、A->C->B->A->...。 別の言い方をすればA->B->Aのように1つ前に位置に戻したりはしない)。

さらに皿4を予想すれば、多分皿2と同じループになり、 皿番号=木の深さの偶奇性でタイプがきまる。

実行順のほうも皿ごとに切り出すと

• 皿1: [0, 2, 4, 6]
• 皿2: [1, 5]
• 皿3: [3]

となり、こちらも2ごと、4ごと(二分木なのでおそらく次は8ごと)、 と法則が見える。 皿nの始点は2^(n-1) - 1で、順番のスパンは2^nだろう。

こうしてみれば、再帰構造で見ることで、手順の列挙ではぐるぐる こんがらがって見えるその解法も、整然とした構造になっていることがよくわかる。

この予想は、上記のコードでsaucerを4や5にして実行すれば 正しいことが判明する(nodejsより、ブラウザのコンソールで で実行すれば、結果がいくら深くなっても展開できるのでよい)。

---

逆に皿の数nと実行順i = 0 ... 2^n - 2 から、 皿番号、移動元、移動先が一意に算出できる。

皿番号のヒントは、実行順の2進数表現にある。 皿ごとの実行順を２進数にすると、以下のようになる:

• 皿1: [0000, 0010, 0100, 0110]
• 皿2: [0001, 0101]
• 皿3: [0011]

下の桁からみて、1桁目が0なら皿1、2桁目で0なら皿2、3桁目で始めて0なら皿3、... の順番となっている。 そして皿sごとでの順序は、この最初の0以下を右シフトして切り詰めた数 k = i >> sになっている。

移動元、移動先は、この皿ごとの順序kと、木の深さd=n-sの偶奇性から決まる。

• dが偶数の場合: [from, to, rest]
• dが奇数の場合: [from, rest, to]

で移動元はk % 3、移動先は(k + 1) % 3になる。

これらをコードでまとめると、以下のようになる:

"use strict";

function hanoi(saucers, from, to, rest) {
    const tables = [[from, to, rest], [from, rest, to]];
    const pmax = (1 << saucers) - 1; // as 2^saucers - 1
    for (let i = 0; i < pmax; i++) {
        const s = 32 - Math.clz32(-~i & ~i); // as (pos of least 0) + 1
        const k = i >> s;
        const table = tables[(saucers - s) % 2];
        const f = table[k % 3], t = table[(k + 1) % 3];
        console.log(`move ${s} from ${f} to ${t}`);
    }
}

hanoi(3, "A", "B", "C");

hanoi-loop.js

"use strict";

function hanoi(saucers, from, to, rest) {
    const tables = [[from, to, rest], [from, rest, to]];
    const pmax = (1 << saucers) - 1; // as 2 ^ saucers - 1
    for (let i = 0; i < pmax; i++) {
        const s = 32 - Math.clz32(-~i & ~i); // as (pos of least 0) + 1
        const k = i >> s;
        const table = tables[(saucers - s) % 2];
        const f = table[k % 3], t = table[(k + 1) % 3];
        console.log(`move ${s} from ${f} to ${t}`);
    }
}

hanoi(3, "A", "B", "C");

hanoi-tree.js

"use strict";

function hanoi(saucer, from, to, rest) {
    if (saucer === 0) return undefined;
    const left = hanoi(saucer - 1, from, rest, to);
    const center = `${from}->${to}`;
    const right = hanoi(saucer - 1, rest, to, from);
    return [left, center, right].filter(e => e);
}

function showtree(tree, depth) {
    return [].concat(...tree.map(
        e => Array.isArray(e) ?
            showtree(e, depth + 1) : [`${"    ".repeat(depth)}${e}`]));
}

console.log(showtree(hanoi(3, "A", "B", "C"), 0).join("\n"));

hanoi.js

"use strict";

function hanoi(saucer, from, to, rest) {
    if (saucer === 0) return;
    hanoi(saucer - 1, from, rest, to);
    console.log(`move ${saucer} from ${from} to ${to}`);
    hanoi(saucer - 1, rest, to, from);
}

hanoi(3, "A", "B", "C");

note:

• when i = 0b010111, -~i & ~i => 0b001000 (same as (i+1) & ~i)
• other way: ~(i+1) & i => 0b000111