はじめに
オラクルの単一SQLクエリでパスカルの三角形を作成します。一つ上のレベルの隣り合う２つの数字を足した数値で三角形をつくるアレですね。
N TRIANGLE
---------- -----------------------------------------------------------
1 1
2 1-1
3 1-2-1
4 1-3-3-1
5 1-4-6-4-1
6 1-5-10-10-5-1
7 1-6-15-20-15-6-1
8 1-7-21-35-35-21-7-1
9 1-8-28-56-70-56-28-8-1
10 1-9-36-84-126-126-84-36-9-1
11 1-10-45-120-210-252-210-120-45-10-1
12 1-11-55-165-330-462-462-330-165-55-11-1
13 1-12-66-220-495-792-924-792-495-220-66-12-1
14 1-13-78-286-715-1287-1716-1716-1287-715-286-78-13-1
15 1-14-91-364-1001-2002-3003-3432-3003-2002-1001-364-91-14-1
クエリの作成
再帰を使うと一見簡単そうにみえますが、レベル毎に増えていく数値を次のレベルに渡すという機能は再帰クエリそのものにはありませんのでひと工夫が必要です。まぁ、最初っから再帰の引数の数を15個にしておけば15レベルまではいけますけど、もうちょっと柔軟性のあるクエリを目指します。
- 再帰（文字列）
- 再帰（コレクション）
- モデル
- 数学的解法
再帰（文字列）
ではまず再帰で素直に作ってみます。レベルによって増加する数値すべてをパラメータとして次のレベルに渡すことができないので、数値をひとまとめの文字列に変換します。次の再帰レベルでは、受け取った文字列を数値に展開して新しいレベルの数値を計算し、また一つの文字列にまとめて次のレベルに渡します。これで再帰のパラメータを増やすことなくつねに一つの文字列で複数の数値の受け渡しができることになります。
WITH n
AS (SELECT /*+ cardinality(200) */ LEVEL rn FROM dual CONNECT BY LEVEL <= 200),
recur (id, line)
AS (SELECT 1, CAST('1' AS VARCHAR2(4000)) FROM dual
UNION ALL
SELECT id + 1,
(SELECT -- 計算で得た新たな行でダッシュ区切り文字列の作成
SUBSTR(SYS_CONNECT_BY_PATH(s, '-'), 2) s
FROM (SELECT -- 展開された前行から各値を計算
rn, s + NVL(LAG(s) over (ORDER BY rn), 0) s
FROM (SELECT -- 前行のダッシュ区切り文字列の展開
rn, SUBSTR(s, DECODE(rn, 1, 1, INSTR(s, '-', 1, rn - 1) + 1),
NVL(NULLIF(INSTR(s, '-', 1, rn), 0), 4000)
- DECODE(rn, 1, 1, INSTR(s, '-', 1, rn - 1) + 1)) s
FROM n,
(SELECT r.line || '-0' s FROM dual) t -- 4段飛び参照なので12c以上
WHERE LENGTH(s) - LENGTH(REPLACE(s, '-', '')) + 1 >= n.rn))
WHERE connect_by_isleaf = 1
START WITH rn = 1
CONNECT BY PRIOR rn + 1 = rn)
FROM recur r
WHERE id < 15) -- 『レベル15まで』
SELECT id,
LPAD(' ', TRUNC(( MAX(LENGTH(line)) over () - LENGTH(line) ) / 2), ' ') || line triangle
FROM recur
ORDER BY id;
ちなみにダッシュ区切り文字列を作る部分に関して、階層サブクエリでなくLISTAGGにしたほうがスッキリするんですが、再帰クエリの制限として集合関数は使用してはいけないということなのでしょうがないですね。実際のところLISTAGGでもちゃんと動くのでスカラーサブクエリの中まで不可なのかは不明ですが、、、。
あと、相関クエリの４段飛び親カラム参照をしているので、12c以上ってことで。(^^)
再帰（コレクション）
もう一つ再帰です。コレクションを使います。TYPEオブジェクトを作らなければならないのが痛いところですがかなりスッキリします。
CREATE TYPE ptl_typ AS object (id NUMBER, value NUMBER);
CREATE TYPE ptl_tbl_typ IS TABLE OF ptl_typ;
WITH recur (n, tbl)
AS (SELECT 1, ptl_tbl_typ(ptl_typ(1,1)) FROM dual
UNION ALL
SELECT r.n + 1,
(SELECT cast(collect(ptl_typ(r1.id, r1.value + nvl(r2.value, 0))) AS ptl_tbl_typ)
FROM TABLE(r.tbl MULTISET UNION ptl_tbl_typ(ptl_typ(r.n + 1, 0))) r1,
TABLE(r.tbl) r2
WHERE r1.id - 1 = r2.id (+))
FROM recur r
WHERE r.n < 15) -- 『レベル15まで』
SELECT n, lpad(' ', trunc((max(length(p)) over () - length(p))/2), ' ') || p triangle
FROM (SELECT n, listagg(value, '-') within GROUP (ORDER BY id) p
FROM recur,
TABLE(tbl)
GROUP BY n);
ここでCOLLECTも集合関数じゃないの？って疑問が出るかもしれないですが、マニュアルでは、COLLECTは分類上Aggregate functionではなくSingle row functionなんですよね。マニュアルに従うと大丈夫ということになるので、まぁ良しとしましょう(^^)。
モデル
では行間参照最強のモデル。
SELECT n, LPAD(' ', TRUNC((MAX(LENGTH(path)) over () - LENGTH(path))/2), ' ') || path triangle
FROM (SELECT * FROM dual
model dimension BY (1 n, 1 r)
MEASURES (1 value, cast('1' AS VARCHAR2(200)) path)
RULES iterate (14) ( -- 『レベル15まで』
value [iteration_number + 2, FOR r FROM 1 TO iteration_number + 2 INCREMENT 1] =
nvl(value [iteration_number + 1, cv() - 1], 0)
+ nvl(value [iteration_number + 1, cv() ], 0),
path [iteration_number + 2, ANY] ORDER BY r DESC =
value [iteration_number + 2, cv()]
|| nullif('-' || path [iteration_number + 2, cv() + 1], '-')))
WHERE r = 1
ORDER BY n;
なんだかんだ言ってやっぱり最強です。実質以下の行だけで計算が終わってるんですよね。すばらしい。
value[iteration_number + 2, FOR r FROM 1 TO iteration_number + 2 INCREMENT 1] =
nvl(value[iteration_number + 1, cv() - 1], 0) + nvl(value[iteration_number + 1, cv()], 0)
数学的解法
調べたところ、パスカルの三角形の各項目は前行を参照せずとも計算で直接求めることができるらしいです。以下のサイトに詳しい説明があります。
パスカルの三角形は二項係数の表であり、二項係数は n! / ( k! * (n - k)! )で求められるので、要は階乗さえ求められればすべて解決と。ふむふむ。
オラクルには階乗どころか総乗（総積）を求める関数すら用意されていませんが、これは再帰を使えば簡単に解決できます。
WITH t
AS (SELECT LEVEL - 1 n FROM dual CONNECT BY LEVEL <= 15),
f(n, c, fct)
AS (SELECT n, 0, 1 FROM t
UNION ALL
SELECT n, c + 1, fct * ( c + 1 ) FROM f WHERE n > c)
SELECT n, fct "N!"
FROM f
WHERE n = c;
N N!
---------- --------------------
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5,040
8 40,320
9 362,880
10 3,628,800
11 39,916,800
12 479,001,600
13 6,227,020,800
14 87,178,291,200
しかし、せっかく数学的解決法なので、以下を参考にもうちょっと数学的にやってみます。
まず、X * Y = EXP(LOG(X * Y))とLOG (X * Y) = LOG(X) + LOG(Y)が成り立つので、X * Y = EXP(LOG(X) + LOG(Y))となり、つまりは総乗は掛け算でなく足し算(SUM)で求められるわけなんですな。へー、なんかそんなことを遠い遠い昔に習ったような気がする、、、。
以下のSQL、3 * 4 * 5 = 60であってますね。ROUNDは誤差対策。ちなみにこの式、Wikipediaページまであります。
select round( exp( sum( ln( n ) ) ) )
from ( select 3 n from dual
union select 4 from dual
union select 5 from dual);
ROUND(EXP(SUM(LN(N))))
----------------------
60
では、この方法で階乗を出してみます。0!計算時にLN(0)がエラーになるのでDECODEで回避しています。
WITH t
AS (SELECT LEVEL - 1 n FROM dual CONNECT BY LEVEL <= 15)
SELECT t2.n,
ROUND(EXP(SUM(DECODE(t1.n, 0, 0, LN(t1.n))))) "N!"
FROM t t1,
t t2
WHERE t1.n <= t2.n
GROUP BY t2.n
ORDER BY t2.n;
N N!
---------- --------------------
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5,040
8 40,320
9 362,880
10 3,628,800
11 39,916,800
12 479,001,600
13 6,227,020,800
14 87,178,291,200
さて、これで必要な数値は揃いました。あとは、それぞれの項目でn! / ( k! * (n - k)! )を計算するだけです。計算の土台となる行をつくってそれぞれの行でn!、k!、(n - k)!に適合するよう階乗テーブルと結合し最終的な数値を算出します。最後に階層で整形して終わり。
WITH t -- 『レベル15まで』
AS (SELECT LEVEL - 1 n FROM dual CONNECT BY LEVEL <= 15),
f
AS (SELECT y.n,
ROUND(EXP(SUM(DECODE(x.n, 0, 0, LN(x.n))))) fct
FROM t x, t y
WHERE x.n <= y.n
GROUP BY y.n)
SELECT n,
LPAD(' ', TRUNC(( MAX(LENGTH(path)) over () - LENGTH(path) ) / 2), ' ')
|| path triangle
FROM (SELECT y.n + 1 n,
SUBSTR(SYS_CONNECT_BY_PATH(fy.fct / ( fx.fct * fn.fct ), '-'), 2) path
FROM t x, t y, f fx, f fy, f fn
WHERE x.n <= y.n -- 土台
AND x.n = fx.n -- k!を得る
AND y.n = fy.n -- n!を得る
AND y.n - x.n = fn.n -- (n - k)!を得る
AND connect_by_isleaf = 1
START WITH x.n = 0
CONNECT BY PRIOR x.n + 1 = x.n AND PRIOR y.n = y.n);
おわりに
一つの問題をいろいろな方法で解くのは勉強になりますね！
以上です。