第1章最小の空き番号（やさしい版） — 関数プログラミングによるアルゴリズム設計の真珠

あるバラバラな自然数の集まりが与えられたとき、その中に含まれていない一番小さい自然数を見つけよう、というのが今回の問題です。

たとえば、コンピュータの中では「番号」がファイルやオブジェクトの名前として使われます。今使われている番号の一覧があるとき、「まだ使われていない一番小さい番号」を割り当てたい、という場面はよくあります。今回の問題はその単純化です。

ポイントもし数字がすでに小さい順にきれいに並んでいれば、先頭から順に見て「抜けている場所」を探すだけです。でも、順番がバラバラだったらどうしましょう？

このリストに含まれていない最小の数はいくつでしょう？（答えは 15 です。）

ぱっと見、「そもそもリストをソートする必要があるのでは？」と思うかもしれません。でも、ソートは一般には線形時間（データの個数に比例した時間）ではできません。それでも、この問題は線形時間で解けます。本章では、そのやり方を2つ紹介します。

方法1：配列を使った解法

まずは仕様を書いてみる

minfree :: [Nat] → Nat minfree xs = head ([0 ..] \\ xs)

Dart // 仕様通りの素朴版: 0, 1, 2, ... と順に「xs に含まれるか」を調べる。O(n^2)。 int minfreeNaive(List<int> xs) { final set = xs.toSet(); for (var i = 0;; i++) { if (!set.contains(i)) return i; } }

ここで us \\ vs は、リスト us から vs に含まれる要素を取り除いたリストです。つまり、「0, 1, 2, ...という無限の数の列から、リスト xs にある数を全部消して、残った先頭の数を返す」というのが仕様です。

これは動きますが、遅いです。長さ n のリストに対して n² に比例する時間がかかってしまいます（各数について「リストに含まれているか？」を毎回チェックするため）。

速くするためのカギ

重要な観察リストの長さが n なら、0 から n までの n+1 個の数のうち、少なくとも1つはリストに含まれていません（鳩の巣原理）。だから、答えは必ず 0 から n の範囲にあります。

チェックリストを作る

search :: Array Int Bool → Int search = length · takeWhile id · elems

Dart // 先頭から true が連続する長さ = 最初に false になる位置。 int search(List<bool> a) { var i = 0; while (i < a.length && a[i]) i++; return i; }

search は「先頭から True が連続している長さ」を返します。これはちょうど「最初の False の位置」と同じです。

チェックリストを作る部分は、Haskell のライブラリ関数 accumArray を使うと線形時間でできます。

checklist :: [Int] → Array Int Bool checklist xs = accumArray (∨) False (0, n) (zip (filter (≤ n) xs) (repeat True)) where n = length xs

Dart // 長さ n+1 のチェックリストを線形時間で構築。 // accumArray の「初期値 false + 論理和で書き込み」に相当。 List<bool> checklist(List<int> xs) { final n = xs.length; final a = List<bool>.filled(n + 1, false); for (final x in xs) { if (x <= n) a[x] = true; } return a; } // これで minfree(xs) = search(checklist(xs)) となる。O(n)。 int minfreeArray(List<int> xs) => search(checklist(xs));

accumArray とは「初期値の入った配列」と「(位置, 値) のリスト」を受け取って、各位置に対して指定した関数で値をまとめながら配列を作る関数です。今回は「∨（論理和）」を使い、初期値 False の配列に True を書き込んでいます。

おまけ：これでソートもできる

ちょっと似た方法で、範囲がわかっているリストなら線形時間でソートもできます。

countlist :: [Int] → Array Int Int countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

Dart // 各数字の出現回数を数える（範囲 0..n の整数向け）。 List<int> countlist(List<int> xs, int n) { final a = List<int>.filled(n + 1, 0); for (final x in xs) { if (0 <= x && x <= n) a[x]++; } return a; }

各数字が何回現れたかを数えて、それを並べれば整列済みリストの完成です。

別の書き方：状態モナドを使う

accumArray を使わず、配列を「1つずつ書き換えていく」やり方もあります。ただしこれは実質的に手続き型プログラミングをしているようなもので、純粋関数型プログラマからはあまり好まれません。

checklist xs = runSTArray (do {a ← newArray (0, n) False; sequence [writeArray a x True | x ← xs, x ≤ n]; return a}) where n = length xs

Dart // Dart では配列は元々可変なので、1つずつ書き換える手続き型版はこう書ける。 // 実質的に上の checklist と同じ動作（純粋関数から見れば局所的な副作用）。 List<bool> checklistImperative(List<int> xs) { final n = xs.length; final a = List<bool>.filled(n + 1, false); for (final x in xs) { if (x <= n) a[x] = true; // 1要素ずつ書き換え } return a; }

方法2：分割統治法による解法

基本的な考え方

ここでは、リストを2つに分けて別々に処理するアイデアを使います。

まず、\\（差集合的な操作）について、いくつかの性質を知っておきましょう。

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) as \\ (bs ++ cs) = (as \\ bs) \\ cs (as \\ bs) \\ cs = (as \\ cs) \\ bs

これらは、集合の演算（∪ と ∖）と同じような法則です。

いま、as と vs が共通要素を持たず、bs と us も共通要素を持たないとします。すると、次の便利な式が成り立ちます。

(as ++ bs) \\ (us ++ vs) = (as \\ us) ++ (bs \\ vs)

境界 b で切り分ける

[0 ..] \\ xs = ([0 .. b−1] \\ us) ++ ([b ..] \\ vs) where (us, vs) = partition (< b) xs

あとは、「左半分（[0..b−1] から us を除いたもの）が空かどうか」で場合分けします。

「左が空か？」を高速に判定する

「左半分が空」ということは、「0 から b−1 までの全ての数が us に入っている」ということです。us の要素はすべて相異なり、しかも全部 b 未満なので、これは単に個数を数えるだけで分かります。

null ([0 .. b−1] \\ us) ≡ length us == b

大事な前提ここでは 入力リストに重複がないこと が本質的に効いています。方法1では重複があってもよかったですが、こちらでは必要です。

再帰の形にまとめる

関数を少し一般化して、「a 以上で最小の空き番号を返す関数」minfrom を作ります。

minfrom :: Nat → [Nat] → Nat minfrom a xs = head ([a ..] \\ xs)

Dart // 仕様: a 以上で xs に含まれない最小の自然数。 int minfromSpec(int a, List<int> xs) { final set = xs.toSet(); for (var i = a;; i++) { if (!set.contains(i)) return i; } }

minfree xs = minfrom 0 xs minfrom a xs | null xs = a | length us == b − a = minfrom b vs | otherwise = minfrom a us where (us, vs) = partition (< b) xs

Dart // b の選び方はまだ抽象。ここでは length で毎回長さを取る素直版。 (List<int>, List<int>) partitionLt(List<int> xs, int b) { final us = <int>[], vs = <int>[]; for (final x in xs) { (x < b ? us : vs).add(x); } return (us, vs); } int minfromDC(int a, List<int> xs) { if (xs.isEmpty) return a; final n = xs.length; final b = a + 1 + n ~/ 2; // 左右バランスする境界 final (us, vs) = partitionLt(xs, b); if (us.length == b - a) { return minfromDC(b, vs); // 左は詰まっている → 右へ } else { return minfromDC(a, us); // 左に穴がある → 左へ } }

境界 b をどう選ぶ？

b は、左右のリストの長さがなるべくバランスするように選びたいです。良い選び方はこれです。

（n = length xs）。この選び方だと、左右どちらに進んでも、次のリストの長さは n/2 以下になります。よって、計算時間 T(n) は、

を満たし、これを解くと T(n) = Θ(n)、つまり線形時間になります。

最終形（長さの再計算を避ける最適化）

毎回 length を呼び直すと無駄なので、リストと一緒にその長さも持ち回します。

minfree xs = minfrom 0 (length xs, xs) minfrom a (n, xs) | n == 0 = a | m == b − a = minfrom b (n − m, vs) | otherwise = minfrom a (m, us) where (us, vs) = partition (< b) xs b = a + 1 + n div 2 m = length us

Dart // 長さ n を引数として持ち回し、length の再計算を避けた最終形。O(n)。 int minfreeDC(List<int> xs) => _minfrom(0, xs.length, xs); int _minfrom(int a, int n, List<int> xs) { if (n == 0) return a; final b = a + 1 + n ~/ 2; final (us, vs) = partitionLt(xs, b); final m = us.length; if (m == b - a) { return _minfrom(b, n - m, vs); } else { return _minfrom(a, m, us); } }

実測結果この分割統治版は、モナドで一つずつ書き換える方法より約2倍速く、accumArray を使う方法より約20%速いそうです。

Dart // 動作確認: 章冒頭のリスト（答えは 15）で 3 種類の実装を呼ぶ。 void main() { final xs = [8, 23, 9, 0, 12, 11, 1, 10, 13, 7, 41, 4, 14, 21, 5, 17, 3, 19, 2, 6]; print(minfreeNaive(xs)); // 15 print(minfreeArray(xs)); // 15 print(minfreeDC(xs)); // 15 }

まとめ

「線形時間で解こう」と聞くと、つい「各要素を定数時間で処理する」方法を考えがちです。でも今回のように、「問題を半分の大きさに分けて再帰する」というアプローチでも線形時間になることがあります。分割統治法は覚えておく価値があります。

関数型 vs 手続き型純粋関数型プログラマは、「定数時間で書き換えられる配列」をそう簡単には使えません。更新には配列サイズの対数時間がかかるのが普通です¹。だから、関数型と手続き型の解のあいだには対数的な差が生じることがあります。ただ、今回のように、よく考えればその差が消えてしまうこともあります。

1公平のため補足すると、手続き型プログラマもまた、定数時間の索引・更新ができるのは配列が小さいときだけだ、ということを知っています。

どんな問題？