« Project Euler : Problem 13 | トップページ | Project Euler : Problem 14 ~ Collatz 問題とメモ化 »

2010年2月20日 (土)

Haskell で「順列」と「組み合わせ」

 "Project Euler" などの数学的な問題を解くときに「辞書順に生成された順列」を使いたい時があります。( ここでいう「辞書順」とは、例えば "[1,2,3]" を関数に渡したときに "[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]" が返ってくることを言います )
 Hasekell には Data.List モジュールに "permutations" という順列を生成する関数があるのですが、これが辞書順の答えを返してくれないんです。"[1,2,3]" を渡すと "[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]" が返ってきます。

 そこで、Haskell の練習も兼ねて自分で作ってみることにしました。
 紙と鉛筆で順列を考える場合のように、樹形図を作っていくイメージです。

permutation :: [a] -> Int -> [[a]] permutation [] _ = [[]] permutation ns size = perm size (length ns - 1) [(ns, [])] where perm 0 _ xs = [a | (_, a) <- xs] perm c n xs = perm (c - 1) (n - 1) $ concatMap (f n) xs f n (xs, ys) = [(as ++ bs, ys ++ [b]) | x <- [0 .. n], let (as, b : bs) = splitAt x xs]
*Main> permutation [1 .. 4] 2 [[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

 ちょっと行数が多い気はしますが、ネットで見つけたいくつかの「辞書順に順列を生成する関数」と比べても 4 〜 5 倍の速さで答えを出せるようなので自分としては満足かなと……。

 

 さらにこの関数をもとに「組み合わせを生成する関数」もつくってみました。

combination :: [a] -> Int -> [[a]] combination [] _ = [[]] combination ns size = comb size [(ns, [])] where comb 0 xs = [a | (_, a) <- xs] comb c xs = comb (c - 1) $ concatMap comb' xs comb' (x : xs, ys) = (xs, ys ++ [x]) : comb' (xs, ys) comb' _ = []
*Main> combination [1 .. 4] 2 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

« Project Euler : Problem 13 | トップページ | Project Euler : Problem 14 ~ Collatz 問題とメモ化 »

Haskell」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/47618987

この記事へのトラックバック一覧です: Haskell で「順列」と「組み合わせ」:

« Project Euler : Problem 13 | トップページ | Project Euler : Problem 14 ~ Collatz 問題とメモ化 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ