第9章

有名人を見つける

（やさしい版） Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）

どんな問題？

パーティに集まった人たちのなかから、「有名人の集まり（celebrity clique）」を見つけ出す問題を考えます。

有名人クリークの定義

集合 P の部分集合 C が「有名人クリーク」だとは、次の2つを両方満たすことをいいます。

ただし C は空ではないとします。今回は「有名人クリークが必ず1つある」と仮定して、それを見つけるプログラムを書くのが目標です。データとして、二人が知り合いかどうかを判定する述語 knows と、パーティの参加者リスト ps（重複なし）が与えられます。

この章の面白いところ 「解があると仮定して見つける」ほうが、「解があるかどうかを確かめる」よりも漸近的に速い、という珍しい例です。前者は線形時間で、後者は最悪でも二乗時間かかります。

この章の進め方

原著では、先生と4人の学生（Anne, Jack, Mary, Theo）の対話で議論が進みます。ここでも対話は残しつつ、途中で「いまどんな話をしているか」の解説を挟みます。

対話：問題の把握と最初のアルゴリズム

先生：おはよう。今日は「パーティの参加者 P のなかから有名人クリーク C を見つける関数プログラム」を書いてもらう。ただし有名人クリークは必ず1つあるとしてよい。

Jack：クリークの人は、クリーク内の他の全員を実際に知っているのですか？ また自分自身は？

先生：前者は定義から「はい」。後者は問題本体には関係ないが、簡単のため「誰もが自分自身は知っている」と仮定してよい。

Theo：これ、指数時間になりそうですよね。大きさ k のクリークを見つけるだけで Ω(nk) かかります。

Anne：それは違うわ。「有名人クリーク」は「単なるクリーク」よりずっと強い条件だもの。有向グラフで言えば、有名人クリークはグラフ全体の頂点からクリーク内の頂点へ矢印が伸びていて、しかもクリーク外への矢印は無い、という追加条件がつくのよ。

Mary：そう。そしてもう一つ大事なのは、有名人クリークは最大でも1つしか存在しないということ。2つあると仮定して c1 ∈ C1、c2 ∈ C2 を取ると、パーティの全員が C2 の人を知っているから c1 は c2 を知っている。でも C1 の人はクリーク内の人しか知らないから c2 ∈ C1。対称性で C1 = C2 になるわ。

ここまでのポイント

問題の形式化と全数探索

Theo が問題を式にします。C が P の有名人クリークとは、∅ ⊂ C ⊆ P であって次を満たすことです。

(∀x ∈ P, y ∈ C :: x knows y ∧ (y knows x ⇒ x ∈ C))

この条件を C ◁ P と略記します。リスト表現なら次の通り。

cs ◁ ps = and [x knows y ∧ (y knows x ⇒ x ∈ cs) | x ← ps, y ← cs]
Dart typedef Knows = bool Function(int x, int y); // cs ◁ ps : cs が ps における有名人クリークの条件を満たすか bool triangle(List<int> cs, List<int> ps, Knows knows) { for (final x in ps) { for (final y in cs) { // x knows y ∧ (y knows x ⇒ x ∈ cs) if (!knows(x, y)) return false; if (knows(y, x) && !cs.contains(x)) return false; } } return true; }

いちばん素朴な解き方は、全部の部分列を並べて、条件を満たすものを拾うことです。

cclique ps = head (filter (◁ps) (subseqs ps)) subseqs [] = [[]] subseqs (x : xs) = map (x:) (subseqs xs) ++ subseqs xs
Dart // 部分列を長さの降順に列挙（Haskell 版と同じ順序） List<List<int>> subseqs(List<int> xs) { if (xs.isEmpty) return [[]]; final x = xs.first; final rest = subseqs(xs.sublist(1)); return [ for (final ys in rest) [x, ...ys], ...rest, ]; } // 素朴版：全部分列を試して最初に◁を満たすものを返す（指数時間） List<int> ccliqueNaive(List<int> ps, Knows knows) { for (final cs in subseqs(ps)) { if (triangle(cs, ps, knows)) return cs; } return const []; }

subseqs は長さの降順に部分列を返すので、cclique ps は「有名人クリークがなければ空リスト、あればその唯一のクリーク」を返します。ただしこれは指数時間です。

対話：二乗時間まで速くする

Jack：効率化の常套手段は、filter を subseqs の生成に融合することです。まず基底ケースは cs ◁ [ ] = True だから filter (◁ [ ]) (subseqs [ ]) = [[ ]]。帰納ケースは次のようになります。

filter (◁ (p : ps)) (subseqs (p : ps)) = {subseqs の定義} filter (◁ (p : ps)) (map (p:) (subseqs ps) ++ subseqs ps) = {filter は ++ に分配される} filter (◁ (p : ps)) (map (p:) (subseqs ps)) ++ filter (◁ (p : ps)) (subseqs ps)

Anne：あとは (p : cs) ◁ (p : ps) と cs ◁ (p : ps) を（cs が ps の部分列で p ∉ cs のとき）簡単にすればいいのよ。

Anne の整理をまとめると、次の2つの補助述語で書き直せます。

cs ◁ (p : ps) = cs ◁ ps ∧ nonmember p cs (p : cs) ◁ (p : ps) = cs ◁ ps ∧ member p ps cs nonmember p cs = and [p knows c ∧ not (c knows p) | c ← cs] member p ps cs = and [x knows p ∧ (p knows x ⇔ x ∈ cs) | x ← ps]
Dart // p は cs の外側の人（cs のメンバー全員を知り、彼らからは知られない） bool nonmember(int p, List<int> cs, Knows knows) { for (final c in cs) { if (!knows(p, c) || knows(c, p)) return false; } return true; } // p を cs に加えて有名人クリークになれるか bool member(int p, List<int> ps, List<int> cs, Knows knows) { for (final x in ps) { // x knows p ∧ (p knows x ⇔ x ∈ cs) if (!knows(x, p)) return false; if (knows(p, x) != cs.contains(x)) return false; } return true; }

これを使って融合を進めると、最終的に次の ccliques が得られます。

cclique = head · ccliques ccliques [] = [[]] ccliques (p : ps) = map (p:) (filter (member p ps) css) ++ filter (nonmember p) css where css = ccliques ps
Dart // 二乗時間版：候補は各段階で高々 2 本に絞れる List<List<int>> ccliques(List<int> ps, Knows knows) { if (ps.isEmpty) return [[]]; final p = ps.first; final rest = ps.sublist(1); final css = ccliques(rest, knows); return [ for (final cs in css) if (member(p, rest, cs, knows)) [p, ...cs], for (final cs in css) if (nonmember(p, cs, knows)) cs, ]; } List<int> ccliqueQuadratic(List<int> ps, Knows knows) => ccliques(ps, knows).first;
この時点の成果 member と nonmember は線形時間、ccliques が返すリストも高々2本（真のクリーク＋空）なので、二乗時間 O(n2) に落とせました。指数時間からの大幅な改善です。

対話：二乗の壁と、そこを突破する発想

Theo：これ以上は無理でしょう。もし劣二乗時間のアルゴリズムがあれば、knows 行列のあるエントリを見ないで済ますことになる。全員が全員を知っている場合を考え、その見ないエントリを false に変えると――結局そのパーティには有名人クリークが存在しなくなり、アルゴリズムは誤った答えを返す。だから最悪ケースでは全エントリを見る必要がある、はずです。

先生：Theo、正しい。ただし問題は「クリークが存在するかを判定せよ」ではない。「存在すると仮定して1つ挙げよ」だ。だから君の反例の場面では、どちらも ps を返せば済む。前者では正解、後者では有名人クリークが無いのだから、何を返しても構わない。

重要な観察 「解の存在を前提にする」ことで、行列の全部を見ずに済むアルゴリズムが可能になります。この章の核心です。

教室が一瞬静まり、学生たちはこの指摘を噛みしめる。

対話：Mary の線形時間アルゴリズム

Mary：Anne の議論から、任意の xs について次が言えます。

xs ◁ (p : ps) ⇒ (xs \\ [p]) ◁ ps

ここで \\ はリスト差です。この事実は「ps にすでにクリーク cs があって、そこに新しい人 p が加わったとき、次のクリーク候補は限られる」ことを意味します。

4通りの場合分け

cs = cclique ps と p の関係で場合分けします。

  1. cs が空のとき（つまり ps にクリークが無い）：新クリーク候補は [ ] か [p]。
    null (cclique ps) ⇒ cclique (p : ps) ∈ {[], [p]}
  2. p が cs のメンバー c を知らない：c は有名人でなくなる。他のメンバーも c を知っているから同様。
    c ∈ cclique ps ∧ not (p knows c) ⇒ cclique (p : ps) ∈ {[], [p]}
  3. p は c を知るが、c は p を知らない：cs がそのままクリーク。
    c ∈ cclique ps ∧ p knows c ∧ not (c knows p) ⇒ cclique (p : ps) = cclique ps
  4. 互いに知っている：p を加えた p : cs がクリーク。
    c ∈ cclique ps ∧ p knows c ∧ c knows p ⇒ cclique (p : ps) ∈ {[], p : cs}

Theo：推論は正しいけど、cclique ps の値を先に知っていないと使えませんよね？ もしかして次のような cclique′ を提案してるんですか？

cclique' = foldr op [] op p cs | null cs = [p] | not (p knows c) = [p] | not (c knows p) = cs | otherwise = p : cs where c = head cs
Dart // 新しい人 p を今の候補クリーク cs の先頭 c と比べて 4 通りに振り分ける List<int> op(int p, List<int> cs, Knows knows) { if (cs.isEmpty) return [p]; final c = cs.first; if (!knows(p, c)) return [p]; // p が c を知らない → c は失格 if (!knows(c, p)) return cs; // c が p を知らない → cs のまま return [p, ...cs]; // 互いに知る → p を加える } // 線形時間版：右畳み込み List<int> ccliquePrime(List<int> ps, Knows knows) => ps.reversed.fold(<int>[], (cs, p) => op(p, cs, knows));

Theo の疑問は、次の (9.1) がなぜ成り立つのか、というものです。

not (null (cclique ps)) ⇒ cclique ps = cclique' ps(9.1)

Mary の帰納法による証明

(9.1) を ps についての帰納法で証明します。

基底ケース [ ]：cclique [ ] = [ ] なので前提が偽になり、(9.1) は自明に成立。

帰納ケース p : ps：cclique (p : ps) が空でないと仮定。cclique ps が空か否かで2通り。

(a) cclique ps が空でないとき、帰納法の仮定から cclique ps = cclique′ ps。

cclique (p : ps) = {先ほどの場合分けと op の定義} op p (cclique ps) = {cclique ps = cclique' ps} op p (cclique' ps) = {cclique' の定義} cclique' (p : ps)

(b) cclique ps が空のときは：

cclique (p : ps) = {仮定と場合分けの最初のケース} [p] = {p が唯一の有名人ゆえ、任意の c ∈ cclique' ps について not (p knows c) となる} op p (cclique' ps) = {同上} cclique' (p : ps)

これで (9.1) が成立し、線形時間で cclique ps が求まることが示されました。

まとめ op は「新しい人 p を今の候補クリークの先頭 c と比較して4通りに振り分ける」だけ。1人あたり定数回の knows 参照で済むので、全体で O(n) です。

対話：形式的な融合則で導く

Anne：単純で美しいけど、Mary の閃きに頼らずに cclique′ を融合則から機械的に導出したいわ。

subseqs も foldr で書ける

subseqs = foldr add [[]] add x xss = map (x:) xss ++ xss
Dart // subseqs を foldr で書き直したもの List<List<int>> add(int x, List<List<int>> xss) => [ for (final ys in xss) [x, ...ys], ...xss, ]; List<List<int>> subseqsFold(List<int> xs) => xs.reversed.fold(<List<int>>[[]], (xss, x) => add(x, xss));

教科書の融合則の限界

教科書の foldr 融合則は次のようなものです。

しかし今回は、filter (◁ps) が ps をパラメータに持つ点と、等式ではなく緩い関係で結びたい点で、そのままでは使えません。

Theo の工夫：パラメータを畳み込む

subseqs′ を「部分列とリスト自身のペア」を返すようにすれば、パラメータ問題は解決します。

subseqs' = foldr step ([], [[]]) step x (xs, xss) = (x : xs, map (x:) xss ++ xss)
Dart // リスト自身と部分列リストのペアを一緒に育てる (List<int>, List<List<int>>) step( int x, (List<int>, List<List<int>>) acc) { final (xs, xss) = acc; return ( [x, ...xs], [ for (final ys in xss) [x, ...ys], ...xss, ], ); } (List<int>, List<List<int>>) subseqsPair(List<int> xs) => xs.reversed.fold((<int>[], <List<int>>[[]]), (acc, x) => step(x, acc));

すると cclique = f · subseqs′。ここで f (ps, css) = head (filter (◁ps) css)。

Mary の一般化された融合則

値の上のなんらかの関係 ⇝ を用意します（中身は問わない）。次の一般化された融合則が、帰納法で簡単に示せます。

f (foldr g a xs) ⇝ foldr h b xs

が任意の有限リスト xs について成り立つのは、f a ⇝ b であって、任意の x, y, z について

f y ⇝ z ⇒ f (g x y) ⇝ h x z

が成り立つとき、です。

Jack の仕上げ：適切な ⇝ の定義

今回は、次の関係が鍵になります。

xs ⇝ ys = not (null xs) ⇒ xs = ys

「左辺が空でなければ、右辺は左辺と等しい」という緩い関係です。示すべきは次の2つ。

head (filter (◁ []) [[]]) ⇝ [] head (filter (◁ ps) css) ⇝ cs ⇒ head (filter (◁(p : ps)) (map (p:) css ++ css)) ⇝ op p cs

そして、これらはまさに Mary の場合分けの推論が示してくれています。

先生の総括 一般化された融合則は、Wadler (1989) の「Theorems for free!」論文にあるパラメトリック性から得られます。この章は「解が存在すると仮定して見つける」ほうが「実際に解かどうかを確かめる」より漸近的に速いという珍しい例です。似た例に多数決投票問題（Morgan 1994, 第18章）がありますが、こちらは確認が線形時間で済むので漸近差はありません。
Dart void main() { // パーティ [0, 1, 2, 3, 4]。有名人クリークは {2, 3}。 // 「クリーク内の互いは知り合い、外部の全員はクリークを知る、 // クリーク側は外部を知らない」というグラフ。 final clique = {2, 3}; bool knows(int x, int y) { if (x == y) return true; // 自分は自分を知る if (clique.contains(x)) return clique.contains(y); // 内→内のみ return clique.contains(y); // 外→内のみ } final ps = [0, 1, 2, 3, 4]; print(ccliqueNaive(ps, knows)); // [2, 3] print(ccliqueQuadratic(ps, knows)); // [2, 3] print(ccliquePrime(ps, knows)); // [2, 3] }

結びに

この問題の実際の由来は次の通りです。著者は元々命令的な形式的プログラム設計の講義でこの問題を思いつき（Kaldewaij 1990 の問題の一般化）、ループ不変条件と1日格闘したものの、十分単純な解に辿り着けず、課題として提示しました。その週末に Sharon Curtis が線形時間解を、学部2年生の Julian Tibble がうまい推論法を発見しました。

「ループと不変条件でできることは、関数的な導出の法則でも同じくらい容易にできるはず」という信念のもと、問題を関数的な設定に翻訳し、上の対話が作られました。その後 2004年9月に Nottingham の WG2.1 会合で試すと、実際の議論も対話の前半をなぞる形で進み、翌日には Andres Löh と Johan Jeuring が線形時間解を発見したそうです。

参考文献

Kaldewaij, A. (1990). Programming the Derivation of Algorithms. Hemel Hempstead: Prentice Hall.

Morgan, C. (1994). Programming from Specifications, 2nd edition. Hemel Hempstead: Prentice Hall.

Wadler, P. (1989). Theorems for free! Fourth International Symposium on Functional Programming Languages and Computer Architecture. ACM Press, pp. 347–59.