ホーム ＞ リレーショナル・データベースの世界 ＞
SQLで数学パズルを解く（組み合わせ論編-問題）
このコーナーは、SQL を使って色々な数学上の問題を解いていくことで、楽しく SQL の勉強をしよう、という趣旨のサイトです。SQL はその本来の用途として、計算向きの言語ではありません。SQL の本領は検索、すなわち与えられた集合から、条件を満たす部分集合を見つけ出すことにあるからです。それゆえ、数学パズルをプログラミング言語を使って解くアルゴリズムは世に多く知られていますが、SQL の解き方は一般的な手続き型言語とはかなり違ったものになります。皆さんも、頭をひねって色々な解法を考えてみてください。
このサイトでは、主に組み合わせ論の分野におけるパズルを主に取り上げます。姉妹編として、「数論編」も参照。
それでは、下準備として組み合わせの要素を含むテーブルを用意しましょう。次のコードを実行してください。
--要素テーブル
CREATE TABLE Elements
(e INTEGER NOT NULL PRIMARY KEY);
INSERT INTO Elements VALUES (1);
INSERT INTO Elements VALUES (2);
INSERT INTO Elements VALUES (3);
INSERT INTO Elements VALUES (4);
INSERT INTO Elements VALUES (5);
--要素テーブルをクリアするときは以下を実行s
DELETE FROM Elements;
とりあえず要素は、5つにしておきましょう。問題によっては、数を変えることもあるかもしれません。解法を考えるときの条件は、以下のように緩くしておきましょう。
- 実装依存の機能を使っても OK。しかしできれば標準 SQL に則っていると望ましい。
- 上で作った要素テーブルは使わなくてもよい。別の補助テーブルを使うのもアリ。
また、問題および解法も随時募集しております。「この問題が解けるか！」という挑戦でも、「こんなエレガントな（or 奇抜な）解法を思いついた」という自慢でも大歓迎です。タレコミ先は、メール、ゲストブック、ブログのいずれからでもどうぞ。
まずは SQL で組み合わせを作る基本をマスターしましょう。組み合わせの種類には、大雑把に、順列／組み合わせ、重複あり／重複なし、の基準によって４つに分類されます。
重複順列とは、いくつかの要素の中から重複を許した要素を、順序を意識して選び出した場合の並びのこと。。
まずはウォーミングアップから。二つ選ぶケースが出来たら、三つ、四つと一般化した場合も考えてみてください。
解答はこちら
順列とは、いくつかの要素の中から相異なる要素を、順序を意識して選び出した場合の並びのこと。
これもやはり、まずは二つ選ぶ簡単なケースから始めましょう。それが出来たら三つ以上に一般化してほしいのですが、気をつけないと条件が膨大になって混乱しがちです。でもうまく整理すると、非常に簡潔にまとめられます。
解答はこちら
重複組み合わせとは、いくつかの要素の集まりからいくつかの要素を選び出す方法で、選ぶ要素に重複を認めるもの。
順列に比べると、組み合わせの方が全般的に簡単に作れます。不等号の性質をうまく利用しましょう。
解答はこちら
組み合わせとは、いくつかの要素の集まりから相異なる要素を選び出す方法のこと。
多分、実務で一番お目にかかるのがこのタイプの組み合わせでしょう。その意味でも、覚えておいて損はありません。
解答はこちら
部分和問題は、ある集合の部分集合の和に関する問題です。SQL で冪集合を作成するには、ちょっと工夫が必要になります。そのため、興味深いアプローチが数多く寄せられました。
部分和問題とは、任意の数の整数の集合から適当な部分集合を選んで、その部分集合の和が与えられた数 N に等しくなるような組み合わせが存在するか調べる問題。
部分和問題は、より一般化した形式である「ナップザック問題」という名前の方が有名かもしれません。例えば、N = 7 とすると、Elements テーブルの 1 〜 5 の集合からは (2, 5) や (1, 2, 4) という部分集合が該当します。こうした「足すと 7 になる」組み合わせを、全て求めてください。
解答はこちら
先ほどの部分和問題の続きです。今度は、母集合の要素が、行方向ではなく列方向で保持されていた場合を考えてみましょう。次のテーブルを使います。
--要素テーブル（列持ち）
CREATE TABLE ElementCols
(e1 INTEGER NOT NULL,
e2 INTEGER NOT NULL,
e3 INTEGER NOT NULL,
e4 INTEGER NOT NULL,
e5 INTEGER NOT NULL);
INSERT INTO ElementCols VALUES(1, 2, 3, 4, 5);
列持ちの構造は、テーブル定義を変更しないと要素の数を増減できず拡張性に乏しいため、実務では極力避けるべきですが、今は純粋に練習問題と思って考えてみてください。
解答はこちら
部分和問題の変奏として、こんな問題はいかがでしょう。
いま、病院で患者の罹患している病気を管理する Paients テーブルがあるとします。このテーブルは、患者一人につき一行という構成になっており、病気に罹患していれば 1、そうでなければ 0 を立てるフラグ列が4つ用意されています。先ほどの問題と同じ列持ち構造のテーブルです。5つ以上の病気を登録できないため実用的ではありませんが、こういう設計はまま見かけます。cost 列は、治療にかかる費用です。
--患者病気テーブル（列持ち）
CREATE TABLE Patients
(name CHAR(16) NOT NULL PRIMARY KEY,
sick_1 INTEGER NOT NULL,
sick_2 INTEGER NOT NULL,
sick_3 INTEGER NOT NULL,
sick_4 INTEGER NOT NULL,
cost INTEGER NOT NULL);
INSERT INTO Patients VALUES('A', 1, 1, 0, 0, 1);
INSERT INTO Patients VALUES('B', 1, 0, 1, 0, 5);
INSERT INTO Patients VALUES('C', 1, 0, 1, 1, 10);
INSERT INTO Patients VALUES('D', 0, 1, 0, 1, 7);
INSERT INTO Patients VALUES('E', 0, 1, 1, 1, 9);
INSERT INTO Patients VALUES('F', 1, 1, 1, 1, 2);
さて、それでは問題です。このテーブルから、ちょうど二つの病気に罹っている患者の治療代の合計を、病気の組み合わせごとに求めてください。この説明だとちょっと分かりにくいので、具体例を挙げましょう。例えば、（病気1, 病気2）のペアを考えるなら、この両方を併発している患者は、A さんと F さんで、治療費は 1 + 2 = 3。同様に、病気3と病気4を併発している患者は、C、E、F の3人なので、合計の治療費は、10 + 9 + 2 = 21となります。糖尿病のような病気にかかると、他の病気も誘発するため、こういう病気の組み合わせの分析は現実的な重要性があります。
二つの組み合わせについて解けたら、三つ、四つの場合にも一般化できるようにしてみてください。
解答はこちら
作成者：ミック
作成日：2007/07/25
最終更新日：2007/08/11
この作品は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。