オラクルの単一SQLクエリでパスカルの三角形をいくつか 

##はじめに

オラクルの単一SQLクエリで[パスカルの三角形](https://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2)を作成します。一つ上のレベルの隣り合う２つの数字を足した数値で三角形をつくるアレですね。

```:パスカルの三角形
         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レベルまではいけますけど、もうちょっと柔軟性のあるクエリを目指します。


- 再帰（文字列）
- 再帰（コレクション）
- モデル
- 数学的解法



###再帰（文字列）

ではまず再帰で素直に作ってみます。レベルによって増加する数値すべてをパラメータとして次のレベルに渡すことができないので、数値をひとまとめの文字列に変換します。次の再帰レベルでは、受け取った文字列を数値に展開して新しいレベルの数値を計算し、また一つの文字列にまとめて次のレベルに渡します。これで再帰のパラメータを増やすことなくつねに一つの文字列で複数の数値の受け渡しができることになります。

```sql:12c以上でよろしく
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以上ってことで。(^^)
> [相関サブクエリから親の親レベルのカラム参照がついにオフィシャルに](https://qiita.com/tlokweng/items/0013f05269209d1e7e55)


###再帰（コレクション）

もう一つ再帰です。コレクションを使います。TYPEオブジェクトを作らなければならないのが痛いところですがかなりスッキリします。

```sql:再帰＋コレクション（11gR2以上）
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``なんですよね。マニュアルに従うと大丈夫ということになるので、まぁ良しとしましょう(^^)。

###モデル

では行間参照最強のモデル。

```sql:モデル(10g以上)
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;
```

なんだかんだ言ってやっぱり最強です。実質以下の行だけで計算が終わってるんですよね。すばらしい。

```sql:
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)
```

###数学的解法

調べたところ、パスカルの三角形の各項目は前行を参照せずとも計算で直接求めることができるらしいです。以下のサイトに詳しい説明があります。

> [パスカルの三角形と最短経路](http://www.mathlion.jp/article/ar103.html)

パスカルの三角形は二項係数の表であり、二項係数は ``n! / ( k! * (n - k)! )``で求められるので、要は階乗さえ求められればすべて解決と。ふむふむ。
オラクルには階乗どころか総乗（総積）を求める関数すら用意されていませんが、これは再帰を使えば簡単に解決できます。

```sql:階乗(再帰)
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
```

しかし、せっかく数学的解決法なので、以下を参考にもうちょっと数学的にやってみます。

> [対数とは何なのかとその公式・メリットについて](https://atarimae.biz/archives/12581)
> [項目の総積を求める](http://d.hatena.ne.jp/nagakura_eil/20090617/p1)

まず、``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ページ](https://en.wikipedia.org/wiki/LogSumExp)まであります。

```sql:

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で回避しています。

```sql:階乗
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)!``に適合するよう階乗テーブルと結合し最終的な数値を算出します。最後に階層で整形して終わり。

```sql:数学的解法
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); 
```

##おわりに

一つの問題をいろいろな方法で解くのは勉強になりますね！

以上です。