はじめに
再帰演習の定番である「ハノイの塔」をSQLで解きます。基本OracleのSQLで記述していますが、特別なことをしているわけではないので、再帰が使えるSQLであればすこしの手直しで簡単に書き換えらます。ということで最後にPostgreSQL版とMySQL版も載せています。
ハノイの塔の再帰アルゴリズム
ハノイの塔には非常に有名な再帰記述アルゴリズムがあります。「複雑そうな動きも再帰で記述するとこんなに簡単になるんだよ」と言える代表格みたいなやつですね。
Hanoi (n, orig, free, dest) {
if (n > 1) Hanoi (n - 1, orig, dest, free);
printf("%s -> %s\n", orig, dest);
if (n > 1) Hanoi (n - 1, free, orig, dest);
}
アルゴリズム等の詳しい解説に関しては下記のサイト等を参考にしてください。他にも「ハノイの塔」で検索すればたくさん出てくると思いますのでここでは簡潔に説明します。
まず上記のHANOI関数ですが、『第一引数(N)個のタイルの山を第二引数(ORIG)から第四引数(DEST)にまとめて移動する』ものであると考えてください。例えば４つのタイルの山がORIGにある状態でHANOI関数を呼ぶと、タイルの山がそのままDESTに移動して帰ってくるイメージです。ルール等は一旦置いておいてHANOI関数はそういう動きをするものだと定義します。
次に内部の再帰コールを見ていきます。先程の4つのタイルの山でHANOI関数を呼んだとしましょう。ここで行われるのは、以下の３つです。
#1. 4つ目のタイルを除いた上3つのタイルの山(N - 1)を『まとめて』ORIGから一旦FREEへ移動する
#2. 4つ目のタイルをORIGからDESTへ移動する。これが実際の動き（出力）となります。
#3. 上記#1でFREEに移動した3つのタイルを『まとめて』FREEからDESTへ移動する。
最後の一つのタイルを除いて、残り３つのタイルをまとめて移動するところがポイントです。これで一番下のタイルを目的地に動かすことができます。そしてさらに移動した残りの３つのタイルをその上に移動して、めでたく完成です。そんなんルール違反だろって思うかもしれませんが、この『まとめて移動』自体が再帰コールなので、またその中で今度は対象となった３つのタイルのうち上２つをまとめて動かし、またそのなかの再帰コールで２つの内上のひとつだけを動かして、最終的に正しく一つずつ動かしているというわけですね。
SQLの再帰クエリでの記述
そのままSQLへ置換
さて、これをSQLの再帰クエリに書き換えてみます。タイルの数を変更するには、SQLコードの二行目の４を変更するだけです。
WITH hanoi (tiles, ln, orig, free, dest) AS (
SELECT 4, -- タイルの数
0, -- ライン番号
'Left', 'Center', 'Right' -- 場所の定義
FROM dual
UNION ALL
SELECT
r.tiles - 1,
r.ln * 2 + m.n,
-- n = 0 のとき (orig, dest, free) : orig -> free
-- n = 1 のとき (free, orig, dest) : free -> dest
DECODE(n, 0, orig, free),
DECODE(n, 0, dest, orig),
DECODE(n, 0, free, dest)
FROM
hanoi r,
(SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE
r.tiles > 1
)
SELECT * FROM hanoi;
TILES LN ORIG FREE DEST
---------- ---------- ------ ------ ------
4 0 Left Center Right
3 0 Left Right Center
3 1 Center Left Right
2 0 Left Center Right
2 1 Right Left Center
2 2 Center Right Left
2 3 Left Center Right
1 0 Left Right Center
1 1 Center Left Right
1 2 Right Center Left
1 3 Left Right Center
1 4 Center Left Right
1 5 Right Center Left
1 6 Left Right Center
1 7 Center Left Right
ここでポイントは２つ。ひとつは再帰の各レベル（Cの場合は一回の関数コール）で２回再帰コールしなければならないため、0と1を持つインラインビューを作って結合し、0のときは上記#1の最初の再帰(ORIG, DEST, FREE)、1のときは#3の２つ目の再帰(FREE, ORIG, DEST)をしています。そしてもうひとつ。SQLではC言語のように再帰コールの途中で結果を出力することができないため、計算後に並び替えてタイルを移動する順番に出力する必要があります。そのためライン番号(LN)をつけて、(TILES, LN)で各行をユニークに識別できるようにしています。
ユニーク番号からステップ番号への置換
そしてその並び替えです。まずは正しいタイルの動きの順番（ステップ番号）をコメントでいれてみます。
TILES LN ORIG FREE DEST ステップ番号
---------- ---------- ------ ------ ------
4 0 Left Center Right <-- #8
3 0 Left Right Center <-- #4
3 1 Center Left Right <-- #12
2 0 Left Center Right <-- #2
2 1 Right Left Center <-- #6
2 2 Center Right Left <-- #10
2 3 Left Center Right <-- #14
1 0 Left Right Center <-- #1
1 1 Center Left Right <-- #3
1 2 Right Center Left <-- #5
1 3 Left Right Center <-- #7
1 4 Center Left Right <-- #9
1 5 Right Center Left <-- #11
1 6 Left Right Center <-- #13
1 7 Center Left Right <-- #15
はい、規則性がさっぱりわかりませんね。では理解しやすようにTILESとLNをツリー図に置き換えてみます。横軸がTILES、縦軸がLNです。それぞれにステップ番号を追加しています。
4 3 2 1 <-- TILES
---------------------------
/ 0 <#1> <-- LN <ステップ番号#>
0 <#2>
/ \ 1 <#3>
/
0 <#4>
/ \ / 2 <#5>
/ \ 1 <#6>
/ \ 3 <#7>
/
0 <#8> / 4 <#9>
\ 2 <#10>
\ / \ 5 <#11>
\ /
1 <#12>
\ / 6 <#13>
\ 3 <#14>
\ 7 <#15>
ステップ番号の規則性
------------------------------
<#8> <#4> <#2> <#1> <-- 各TILESでLN=0 = 2 ^ (tiles - 1)
+ + +
8 4 2 <-- LN増加に対する増加 = 2 ^ tiles
(TILES,LN)とステップ番号の関連性が見えてきました。TILES 4, 3, 2, 1それぞれにおいてLNが0であるときにスッテプ番号が8, 4, 2, 1となっています。これは、2 ^ (TILES - 1)で表されます。さらに各TILESでLNが一つ増えるとステップ番号がそれぞれ、TILESが1では2の増加、TILESが2では4の増加、TILESが3では8の増加となります。つまり(2 ^ TILES)の増加です。したがって(TILES, LN)からステップ番号の変換をSQLで表すと、POWER(2, tiles - 1) + LN * POWER (2, tiles)となります。(追記:表記の間違い訂正しました)
以上の計算を最後の表示に組み込んでハノイの塔の解法ができあがります。
WITH hanoi (tiles, ln, orig, free, dest) AS (
SELECT
4, 0, 'Left', 'Center', 'Right'
FROM dual
UNION ALL
SELECT
r.tiles - 1,
r.ln * 2 + m.n,
DECODE(n, 0, orig, free),
DECODE(n, 0, dest, orig),
DECODE(n, 0, free, dest)
FROM
hanoi r,
(SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE
r.tiles > 1
)
SELECT POWER(2, tiles - 1) + ln * POWER (2, tiles) step, -- ステップ番号
tiles tile,
orig || ' -> ' || dest action -- タイルの移動
FROM hanoi
ORDER BY step;
STEP TILE ACTION
---------- ---------- ----------------
1 1 Left -> Center
2 2 Left -> Right
3 1 Center -> Right
4 3 Left -> Center
5 1 Right -> Left
6 2 Right -> Center
7 1 Left -> Center
8 4 Left -> Right
9 1 Center -> Right
10 2 Center -> Left
11 1 Right -> Left
12 3 Center -> Right
13 1 Left -> Center
14 2 Left -> Right
15 1 Center -> Right
視覚図への置換
これで一応完成といえば完成なんですか、やっぱり動きの指示だけだといまいち分かりにくいので、さらに再帰クエリを追加して視覚的な図にしてみましょう。
col left for a21 jus right
col center for a21 jus right
col right for a21 jus right
WITH
-- ハノイの塔の再帰
hanoi (tiles, ln, orig, free, dest) AS (
SELECT -- タイル数
4, 0, 'Left', 'Center', 'Right'
FROM dual
UNION ALL
SELECT
r.tiles - 1,
r.ln * 2 + m.n,
DECODE(n, 0, orig, free),
DECODE(n, 0, dest, orig),
DECODE(n, 0, free, dest)
FROM hanoi r,
(SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE r.tiles > 1
),
-- 開始時のタイルの山を作成 e.g. 1-2-3-4-
pile(n, s, m) AS (
SELECT
1, CAST('1-' AS VARCHAR2(100)), MAX(tiles)
FROM hanoi
UNION ALL
SELECT
n + 1, s || TO_CHAR(n + 1) || '-', m
FROM pile
WHERE n < m
),
-- 各行でのタイルの移動に応じたタイルの山の再生成
display (step, left, center, right, target) AS (
SELECT
0,
s,
CAST(NULL as VARCHAR2(100)), -- CASTしないと意図しない動きになることがある
CAST(NULL as VARCHAR2(100)), -- なんとなくオラクルのバグっぽい
CAST(NULL as VARCHAR2(10))
FROM pile
WHERE n = m
UNION ALL
SELECT
p.step,
CASE -- LEFT
WHEN p.orig = 'Left' THEN REGEXP_REPLACE(left, '^\d+-', '')
WHEN p.dest = 'Left' THEN p.tile_no || '-' || left
ELSE left
END,
CASE -- CENTER
WHEN p.orig = 'Center' THEN REGEXP_REPLACE(center, '^\d+-', '')
WHEN p.dest = 'Center' THEN p.tile_no || '-' || center
ELSE center
END,
CASE -- RIGHT
WHEN p.orig = 'Right' THEN REGEXP_REPLACE(right, '^\d+-', '')
WHEN p.dest = 'Right' THEN p.tile_no || '-' || right
ELSE right
END,
p.dest
FROM display d,
(SELECT -- 並び順の計算
POWER(2, tiles - 1) + ln * POWER(2, tiles) step,
tiles tile_no, orig, dest, ln
FROM hanoi) p
WHERE d.step + 1 = p.step
)
-- タイルの山を右寄せで出力 (タイル数が10を超える場合はサイズを広げる)
SELECT
step,
LPAD(DECODE(target, 'Left', '*') || RTRIM(left, '-'), 21, ' ') left,
LPAD(DECODE(target, 'Center', '*') || RTRIM(center, '-'), 21, ' ') center,
LPAD(DECODE(target, 'Right', '*') || RTRIM(right, '-'), 21, ' ') right
FROM display
ORDER BY step;
以下が出力となります。ついでなので、確認しやすいように移動したタイルには＊をつけてみました。かなり視覚的にわかりやすくなったのではないでしょうか。小さな数の上に大きな数が来ることなく左の山を右に移動できていますね。
STEP LEFT CENTER RIGHT
---------- --------------------- --------------------- ---------------------
0 1-2-3-4
1 2-3-4 *1
2 3-4 1 *2
3 3-4 *1-2
4 4 *3 1-2
5 *1-4 3 2
6 1-4 *2-3
7 4 *1-2-3
8 1-2-3 *4
9 2-3 *1-4
10 *2 3 1-4
11 *1-2 3 4
12 1-2 *3-4
13 2 *1 3-4
14 1 *2-3-4
15 *1-2-3-4
PostgreSQLとMySQL
PostgreSQLとMySQLにも書き換えてみました。大きな変更はありません。せいぜい文字連結をCONCATにしたりDECODEをCASE WHENにしたり。ただ、CASTしないとエラーになる場所がデータベースによって異なるというのが面白いところですね。
PostgreSQL版
PostgreSQL 11.0で確認しました。
WITH RECURSIVE hanoi (tiles, ln, orig, free, dest) AS (
SELECT
4, 0, 'Left', 'Center', 'Right'
UNION ALL
SELECT
r.tiles - 1,
r.ln * 2 + m.n,
CASE WHEN n = 0 THEN orig ELSE free END,
CASE WHEN n = 0 THEN dest ELSE orig END,
CASE WHEN n = 0 THEN free ELSE dest END
FROM
hanoi r,
(SELECT 0 n UNION ALL SELECT 1) m
WHERE
r.tiles > 1
),
pile(n, s, m) AS (
SELECT
1, '1-', MAX(tiles)
FROM hanoi
UNION ALL
SELECT
n + 1, s || n + 1 || '-' , m
FROM pile
WHERE n < m
),
display (step, left_, center_, right_, target) AS (
SELECT
0, s, '', '', ''
FROM pile
WHERE n = m
UNION ALL
SELECT
p.step,
CASE -- LEFT
WHEN p.orig = 'Left' THEN REGEXP_REPLACE(left_, '^\d+-', '')
WHEN p.dest = 'Left' THEN p.tile_no || '-' || left_
ELSE left_
END,
CASE -- CENTER
WHEN p.orig = 'Center' THEN REGEXP_REPLACE(center_, '^\d+-', '')
WHEN p.dest = 'Center' THEN p.tile_no || '-' || center_
ELSE center_
END,
CASE -- RIGHT
WHEN p.orig = 'Right' THEN REGEXP_REPLACE(right_, '^\d+-', '')
WHEN p.dest = 'Right' THEN p.tile_no || '-' || right_
ELSE right_
END,
p.dest
FROM display d,
(SELECT
CAST(POWER(2, tiles - 1) + ln * POWER(2, tiles) AS INTEGER) step,
tiles tile_no, orig, dest, ln
FROM hanoi) p
WHERE d.step + 1 = p.step
)
SELECT
step,
LPAD(CASE WHEN target = 'Left' THEN '*' ELSE '' END || RTRIM(left_, '-'), 21, ' ') left_,
LPAD(CASE WHEN target = 'Center' THEN '*' ELSE '' END || RTRIM(center_, '-'), 21, ' ') center_,
LPAD(CASE WHEN target = 'Right' THEN '*' ELSE '' END || RTRIM(right_, '-'), 21, ' ') right_
FROM display
ORDER BY step;
MySQL版
MySQL 8.0.13で確認しました
WITH RECURSIVE hanoi (tiles, ln, orig, free, dest) AS (
SELECT
4, 0,
CAST('Left' as char(10)),
CAST('Center' as char(10)),
CAST('Right' as char(10))
UNION ALL
SELECT
r.tiles - 1,
r.ln * 2 + m.n,
CASE WHEN n = 0 THEN orig ELSE free END,
CASE WHEN n = 0 THEN dest ELSE orig END,
CASE WHEN n = 0 THEN free ELSE dest END
FROM
hanoi r,
(SELECT 0 n UNION ALL SELECT 1) m
WHERE
r.tiles > 1
),
pile(n, s, m) AS (
SELECT
1, CAST('1-' AS CHAR(100)), MAX(tiles)
FROM hanoi
UNION ALL
SELECT
n + 1, CONCAT(s, n + 1, '-'), m
FROM pile
WHERE n < m
),
display (step, left_, center_, right_, target) AS (
SELECT
0,
s,
CAST('' AS CHAR(100)),
CAST('' AS CHAR(100)),
CAST('' AS CHAR(100))
FROM pile
WHERE n = m
UNION ALL
SELECT
p.step,
CASE -- LEFT
WHEN p.orig = 'Left' THEN CAST(REGEXP_REPLACE(left_, '^[0-9]+-', '') AS CHAR(100))
WHEN p.dest = 'Left' THEN CONCAT(p.tile_no, '-', left_)
ELSE left_
END,
CASE -- CENTER
WHEN p.orig = 'Center' THEN CAST(REGEXP_REPLACE(center_, '^[0-9]+-', '') AS CHAR(100))
WHEN p.dest = 'Center' THEN CONCAT(p.tile_no, '-', center_)
ELSE center_
END,
CASE -- RIGHT
WHEN p.orig = 'Right' THEN CAST(REGEXP_REPLACE(right_, '^[0-9]+-', '') AS CHAR(100))
WHEN p.dest = 'Right' THEN CONCAT(p.tile_no, '-', right_)
ELSE right_
END,
p.dest
FROM display d,
(SELECT
POWER(2, tiles - 1) + ln * POWER(2, tiles) step,
tiles tile_no, orig, dest, ln
FROM hanoi) p
WHERE d.step + 1 = p.step
)
SELECT
step,
LPAD(CONCAT(CASE WHEN target = 'Left' THEN '*' else '' END, TRIM('-' from left_)), 21, ' ') left_,
LPAD(CONCAT(CASE WHEN target = 'Center' THEN '*' else '' END, TRIM('-' from center_)), 21, ' ') center_,
LPAD(CONCAT(CASE WHEN target = 'Right' THEN '*' else '' END, TRIM('-' from right_)), 21, ' ') right_
FROM display
ORDER BY step;
##おわりに
SQL言語の再帰は他の言語と比べると細かい制御はできないですが、再帰のなかったころに比べてSQL単体でできることが相当に広がりました。いわゆる再帰パズルを解くことによってSQLでも再帰に親しめるのではないかと思います。
以上です。