01

04

[Haskell] ある集合の、すべての部分集合を求める。

2013.01.04(18:47)

世界で闘うプログラミング力を鍛える150問
http://www.amazon.co.jp/dp/4839942390/
の問題9.4 をHaskellで解いてみた。

問題 9.4 ある集合の、すべての部分集合を返すメソッドを書いてください。

Haskellなので、リストを与えて、そのリストの要素の部分集合のリストを求める問題として解いてみた。

{-# OPTIONS -Wall -Werror #-}

module Subset where
import Test.HUnit
import Test.QuickCheck

import Control.Monad (filterM)

-- | ------------- 世界で闘うプログラミング力を鍛える150問 -----------------
-- | 問題 9.4 ある集合の、すべての部分集合を返すメソッドを書いてください。

-- | filterMを使えば2行で書けるけど、
-- | それでは面白くないので、再帰を使って書いてみたけど、4行で書ける。

-- | xsの部分集合は、xsの1つ1つの要素がある場合とない場合の
-- | すべての場合を尽くしたものである。
subset1 :: [a]->[[a]]
subset1 xs = filterM (\_->[True,False]) xs

-- | []の部分集合は、[[]]
-- | (x:xs)の部分集合は、xsの部分集合の要素すべてにxを加えたもの ++ xsの部分集合
subset2 :: [a]->[[a]]
subset2 [] = [[]]
subset2 (x:xs) = (map (\ys->x:ys) prev) ++ prev
                 where prev = subset2 xs

-- | ------------------ ユニットテスト ----------------------
-- | クイックソート
qsort :: (Ord a) => [a] -> [a]  
qsort []     = []  
qsort (x:xs) = qsort left ++ [x] ++ qsort right
               where left  = filter (< x)  xs  
                     right = filter (>= x) xs  

subsetTest :: Test
subsetTest = test [
      (qsort $ subset2 ([1..2]::[Int])) ~=? 
      (qsort [[1,2],[1],[2],[]]),
      (qsort $ subset2 ([1..3]::[Int])) ~=? 
      (qsort [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]),
      True ~=? True
  ]

subsetIntTest :: Int -> Test
subsetIntTest n = test [
      (qsort $ subset2 list) ~=? (qsort $ subset1  list),
      True ~=? True
  ] where list = ([1..n]::[Int])

runSubsetIntTest :: [Int] -> IO ()
runSubsetIntTest [] = return ()
runSubsetIntTest (x:xs) = do
   _ <- runTestTT $ subsetIntTest x
   runSubsetIntTest xs

-- | ------------------ quickCheck ----------------------
prop_subset :: Int->Property
prop_subset n =
      (n > 0 && n < 10) 
      ==> (subset1 [0..n]) == (subset2 [0..n])

-- | ------------------ main ----------------------
main :: IO ()
main = do
    print $ subset1 ([1,2,3]::[Int])
    print $ subset2 ([1,2,3]::[Int])
    _ <- runTestTT subsetTest
    runSubsetIntTest [1..10]
    quickCheck prop_subset
    return ()



実行速度を手動で測ってみた。
> :reload
Ok, modules loaded: Subset.
> length $ subset1 [1..24]
16777216
it :: Int
(4.68 secs, 3624150388 bytes)
> length $ subset2 [1..24]
16777216
it :: Int
(1.76 secs, 1208063292 bytes)

プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示