部分和問題をSQLで解く

サービス終了のお知らせ - Yahoo!ジオシティーズ
部分和問題

部分和問題とは、任意の数の整数の集合から適当な部分集合を選んで、その部分集合の和が与えられた数 N に等しくなるような組み合わせが存在するか調べる問題。

リンク先の例だと、1以上5以下の整数の集合から、1つ以上選んだ整数の合計が7になる組合せをあげる、というものでした。
解答について、詳しくは解答ページを見ていただくとして、

しかし、n 個の要素を含む集合について n 回クエリを発行せねばならないというのも大変です。うまく一つの SQL で解く方法はないでしょうか？

と、あったもので、気になって実際に自分でSQLを書いてみました。

組合せについて考える

そもそも、クエリをn回発行するのは、「1個以上の整数を選択する」と考えるから1個の場合、2個の場合、3個の場合。。。。。。と場合わけをしなければいけないのであって、「n個のうち、選択される整数と選択されない整数の組合せ」と考えれば、一回のクエリで全部の組合せがとれるんじゃないか、と思ったわけです。
わかりにくいですよね、自分でも何言ってんだかよくわかんないです。
ともかく、SQLを書いてみました。
あ、そうだ。今回、MySQLでしか確認してないんで、MySQLでしか使えないものとか使ってる可能性あります。

下準備

まず、選択する・しないはbool値なので、0と1の数を用意する。
ついでに、1から5までの集合のテーブルもつくっておく。

CREATE TEBLE bool(id int not null);
INSERT INTO bool VALUES (1), (0);
CREATE TEBLE num5(id int not null);
INSERT INTO num5 VALUES (1), (2), (3), (4), (5);

「n個のうち、選択される整数と選択されない整数の組合せ」

次に、今回の問題に合わせて、5個の組合せを作る。

SELECT * FROM bool a, bool b, bool c, bool d, bool e;
+----+----+----+----+----+
| id | id | id | id | id |
+----+----+----+----+----+
|  0 |  0 |  0 |  0 |  0 | 
|  1 |  0 |  0 |  0 |  0 | 
|  0 |  1 |  0 |  0 |  0 | 
|  1 |  1 |  0 |  0 |  0 | 
|  0 |  0 |  1 |  0 |  0 | 
(中略)
|  0 |  0 |  1 |  1 |  1 | 
|  1 |  0 |  1 |  1 |  1 | 
|  0 |  1 |  1 |  1 |  1 | 
|  1 |  1 |  1 |  1 |  1 | 
+----+----+----+----+----+
32 rows in set (0.10 sec)

さて、ここから、どうするか。
このidの縦列に左から1,2,3,4,5を割り振らなくてはいけない。

組合せと実際の数字を関連付ける

さっきのクエリを元に、こんな感じにjoinする。

SELECT *
  FROM (
    SELECT a.id a, b.id b, c.id c, d.id d, e.id e
      FROM bool a, bool b, bool c, bool d, bool e
  ) as f
  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 1
    ) as n1
    ON a = 1
  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 2
    ) as n2
    ON b = 1
  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 3
    ) as n3
    ON c = 1
  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 4
    ) as n4
    ON d = 1
  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 5
    ) as n5
    ON e = 1
;

+---+---+---+---+---+------+------+------+------+------+
| a | b | c | d | e | id   | id   | id   | id   | id   |
+---+---+---+---+---+------+------+------+------+------+
| 0 | 0 | 0 | 0 | 0 | NULL | NULL | NULL | NULL | NULL | 
| 1 | 0 | 0 | 0 | 0 |    1 | NULL | NULL | NULL | NULL | 
| 0 | 1 | 0 | 0 | 0 | NULL |    2 | NULL | NULL | NULL | 
| 1 | 1 | 0 | 0 | 0 |    1 |    2 | NULL | NULL | NULL | 
| 0 | 0 | 1 | 0 | 0 | NULL | NULL |    3 | NULL | NULL | 
(中略)
| 1 | 1 | 0 | 1 | 1 |    1 |    2 | NULL |    4 |    5 | 
| 0 | 0 | 1 | 1 | 1 | NULL | NULL |    3 |    4 |    5 | 
| 1 | 0 | 1 | 1 | 1 |    1 | NULL |    3 |    4 |    5 | 
| 0 | 1 | 1 | 1 | 1 | NULL |    2 |    3 |    4 |    5 | 
| 1 | 1 | 1 | 1 | 1 |    1 |    2 |    3 |    4 |    5 | 
+---+---+---+---+---+------+------+------+------+------+
32 rows in set (0.00 sec)

大分目的に近付いている気がする。
さらに、この後足し算をすることを考えると、NULLは邪魔なので0になおしておく。

SELECT
  a
, b
, c
, d
, e
, coalesce(n1.id, 0) n1
, coalesce(n2.id, 0) n2
, coalesce(n3.id, 0) n3
, coalesce(n4.id, 0) n4
, coalesce(n5.id, 0) n5
  FROM (...(以下同じ)

+---+---+---+---+---+------+------+------+------+------+
| a | b | c | d | e | n1   | n2   | n3   | n4   | n5   |
+---+---+---+---+---+------+------+------+------+------+
| 0 | 0 | 0 | 0 | 0 |    0 |    0 |    0 |    0 |    0 | 
| 1 | 0 | 0 | 0 | 0 |    1 |    0 |    0 |    0 |    0 | 
| 0 | 1 | 0 | 0 | 0 |    0 |    2 |    0 |    0 |    0 | 
| 1 | 1 | 0 | 0 | 0 |    1 |    2 |    0 |    0 |    0 | 
| 0 | 0 | 1 | 0 | 0 |    0 |    0 |    3 |    0 |    0 | 
(中略)
| 1 | 1 | 0 | 1 | 1 |    1 |    2 |    0 |    4 |    5 | 
| 0 | 0 | 1 | 1 | 1 |    0 |    0 |    3 |    4 |    5 | 
| 1 | 0 | 1 | 1 | 1 |    1 |    0 |    3 |    4 |    5 | 
| 0 | 1 | 1 | 1 | 1 |    0 |    2 |    3 |    4 |    5 | 
| 1 | 1 | 1 | 1 | 1 |    1 |    2 |    3 |    4 |    5 | 
+---+---+---+---+---+------+------+------+------+------+
32 rows in set (0.00 sec)

いい感じ。

仕上げ

後は、n1からn5までを足し算して、7になる組合せを見付ければ良いだけ。

SELECT
  n1
, n2
, n3
, n4
, n5
  FROM (
    SELECT
      a
    , b
    , c
    , d
    , e
    , coalesce(n1.id, 0) n1
    , coalesce(n2.id, 0) n2
    , coalesce(n3.id, 0) n3
    , coalesce(n4.id, 0) n4
    , coalesce(n5.id, 0) n5
      FROM (
        SELECT a.id a, b.id b, c.id c, d.id d, e.id e
          FROM bool a, bool b, bool c, bool d, bool e
      ) as f
      LEFT JOIN (
        SELECT *
          FROM num5
          WHERE id = 1
        ) as n1
        ON a = 1
      LEFT JOIN (
        SELECT *
        FROM num5
        WHERE id = 2
      ) as n2
      ON b = 1
      LEFT JOIN (
        SELECT *
          FROM num5
          WHERE id = 3
        ) as n3
        ON c = 1
      LEFT JOIN (
        SELECT *
          FROM num5
          WHERE id = 4
        ) as n4
        ON d = 1
      LEFT JOIN (
        SELECT *
          FROM num5
          WHERE id = 5
        ) as n5
        ON e = 1
  ) as ssp
  WHERE
    n1 + n2 + n3 + n4 + n5 = 7
;

+------+------+------+------+------+
| n1   | n2   | n3   | n4   | n5   |
+------+------+------+------+------+
|    1 |    2 |    0 |    4 |    0 | 
|    0 |    0 |    3 |    4 |    0 | 
|    0 |    2 |    0 |    0 |    5 | 
+------+------+------+------+------+
3 rows in set (0.01 sec)

できたーっ！

蛇足

本当言うと、もうちょっとすっきりと書けるんじゃないかなーと思っています。

  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 1
    ) as n1
    ON a = 1

これを5回書いている辺り。
でも、今回はこの方法しか思い付かなかったです。うーん。

さらに蛇足

ちなみに、今回、この思考にたどり着くまでに、どんなクエリを書いたかって言うと。

SELECT n1.id, n2.id, n3.id, n4.id, n5.id
  FROM num5 n1, num5 n2, num5 n3, num5 n4, num5 n5
  WHERE
    coalesce(n1.id,-99) < coalesce(n2.id,-98)
  AND
    coalesce(n2.id,-98) < coalesce(n3.id,-97)
  AND
    coalesce(n3.id,-97) < coalesce(n4.id,-96)
  AND
    coalesce(n4.id,-96) < coalesce(n5.id,-95)
  AND
    ( coalesce(n1.id,0)
    + coalesce(n2.id,0)
    + coalesce(n3.id,0)
    + coalesce(n4.id,0)
    + coalesce(n5.id,0) ) = 7;

coalesceだらけ。
一目見ただけで、思考の迷宮をさまよっていたことが伺えるひどいSQLです。
確かに、coalesceは便利だけれどもさ、この使い方ってどうよ。

追記

  LEFT JOIN (
    SELECT *
      FROM num5
      WHERE id = 1
    ) as n1
    ON a = 1

この部分は

  LEFT JOIN (
    SELECT 1 as id
    ) as n1
    ON a = 1

にしちゃえば良いんだ。
それと、蛇足であげたcoalesceだらけのSQLですが、あれの前提になっているnum5テーブルは、今回使用したnum5テーブルとちょっと違っています。

CREATE TABLE num5(id int);
INSERT INTO num5 VALUES (NULL), (1), (2), (3), (4), (5);

という具合に、NULLがあるのでした。
1から5までと、どの数字も選択しない、というのを現すとこうなるかなーと思って、そこからあのcoalesceだらけが生まれたのでした。
今まであやふやだったのに、coalesceの綴り覚えちゃった。