順列と組み合わせ

Haskell で順列と組み合わせを列挙するプログラムを検索した。効率は別として記述がわかりやすいものを選んでみた。定石のようなのでメモしておく。

import Data.List

perm :: Eq a => [a] -> Int -> [[a]]
perm [] _ = [[]]
perm _ 0 = []
perm xs 1 = [[x] | x <- xs]
perm xs n = concat [map (x:) (perm (delete x xs) (n-1)) | x <- xs]

comb :: Ord a => [a] -> Int -> [[a]]
comb xs n = nub . map sort $ perm xs n

実行例

Main> perm "abcd" 3
["abc","abd","acb","acd","adb","adc","bac","bad","bca","bcd","bda","bdc","cab","cad","cba","cbd","cda","cdb","dab","dac","dba","dbc","dca","dcb"]
Main> comb "abcd" 3
["abc","abd","acd","bcd"]
Main> comb "hello" 3
["ehl","eho","hll","hlo","ell","elo","llo"]

高階関数と合成関数はほんとうに便利だ。
[PR]
by tnomura9 | 2011-06-10 17:15 | Haskell | Comments(0)
<< 川渡りパズル ピンクレディー >>