PFAD(1): The smallest free number

与えられた自然数リストの中に存在しない最小の自然数を求める問題。(ここでの自然数は 0 から始まる。)

素朴には、以下のように実装できる。

minfree :: [Int] -> Int
minfree xs = head $ [0..] \\ xs

(\\) :: Eq a => [a] -> [a] -> [a]
us \\ vs = filter (`notElem` vs) us)

us と vs の長さをそれぞれ N と M とすると、(\\) の計算量は O(NM) となる。ちなみに Data.List での定義は、もう少し効率がよくなっている。

(\\) :: (Eq a) => [a] -> [a] -> [a]
(\\) = foldl (flip delete)

とにかく (\\) は効率が悪いので、minfree からなくしたい。(++) と head の性質を使って、(\\) をなくすのが、本章の本質である。

as と vs に共通要素がなく、bs と us にも共通要素がなければ、以下の性質が成り立つ。

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

蛇足：計算量は (\\) よりも (++) の方が少ない。よって、これは等式であるにも関わらず、左辺よりも右辺の方が計算量が少ない。この性質を使って計算量を落とす方法をセミリングヒュージョンというが、この章には関係なかった。以下のように head の性質を用いて、右辺の一方の式を削除し、他方のみを計算するという手法を使う。

minfree に出てきた [0..] \\ xs という式は、任意の自然数 b を用いて以下のように変形できる。

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

なお、Data.List での partition の定義は以下の通りで、計算量は O(N) である。

partition               :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs = foldr (select p) ([],[]) xs

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a])
select p x ~(ts,fs) | p x       = (x:ts,fs)
                    | otherwise = (ts, x:fs)

ちなみに、"~" は遅延パターン。

次に考えたいのは head $ ([0..b-1] \\ us) ++ ([b..] \\ vs) である。head $ xs ++ ys は、以下のように変形できる。

head $ xs ++ ys = if null xs then head ys else head xs

よって、minfree xs は、任意の b があると仮定して、以下のように変形できる。

-- minfree xs =
--   head $ [0..] \\ xs
--     ↓
--   head $ ([0..b-1] \\ us) ++ ([b..] \\ vs)
--     ↓
--   if null ([0..b-1] \\ us) then head ([b..] \\ vs) then head ([0..b-1] \\ us)
minfree xs
  | null ([0..b-1] \\ us) = head $ [b..] \\ vs
  | otherwise             = head $ [0..] \\ us
  where
    (us,vs) = partition (< b) xs
    b = undefined

次は、null の中の (\\) をなくす。us は、b より小さい自然数のリストだから、us の長さが b であれば、[0..b-1]と同じリストとなり、(\\) を取ると空リストになる。よって、

minfree xs
  | length us == b = head $ [b..] \\ vs
  | otherwise      = head $ [0..] \\ us
  where
    (us,vs) = partition (< b) xs
    b = undefined

最後に、右辺の(\\) をなくそう。補助関数 minfrom を以下のように定義する。minfrom は、無限リストの開始の値を引数に取る。

minform a xs = head $ [a..] \\ xs

minfree と同様に、これは以下のように変形できる。

minfrom a xs
  | length us == b - a = head $ [b..] \\ vs
  | otherwise          = head $ [a..] \\ us
  where
    (us,vs) = partition (< b) xs
    b = undefined

minfrom の定義から、さらに再帰的に変形できる。(再帰を止めることを忘れないこと。)

minfrom :: Int -> [Int] -> Int
minfrom a xs
  | null xs            = a
  | length us == b - a = minfrom b vs
  | otherwise          = minfrom a us
  where
    (us,vs) = partition (< b) xs
    b = undefined

b を以下のように二分割するような値に取る。

minfrom :: Int -> [Int] -> Int
minfrom a xs
  | null xs            = a
  | length us == b - a = minfrom b vs
  | otherwise          = minfrom a us
  where
    (us,vs) = partition (< b) xs
    b = a + 1 + n `div` 2
    n = length xs

最後に、あるリストに対して length が複数回呼ばれないように、以下のように変形する。

minfrom :: Int -> (Int,[Int]) -> Int
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

minfrom を使うと、minfree は最終的に以下のように定義できる。

minfree :: [Int] -> Int
minfree xs = minfrom 0 (length xs, xs)

この minfree の計算量は O(N) だそうだ。

あどけない話

Internet technologies

PFAD(1): The smallest free number