「ハノイの塔」を解く手順は、再帰関数でかくと以下のようになる:
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進数表現にある。 皿ごとの実行順を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");
note:
i = 0b010111
,-~i & ~i
=>0b001000
(same as(i+1) & ~i
)~(i+1) & i
=>0b000111