順列
>>> import Data.List
>>> permutations [1,2,3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
組み合わせ
comb :: Int -> [a] -> [[a]]
comb 0 xs = [[]]
comb _ [] = []
comb n (x:xs) = [x:y | y <- comb (n-1) xs] ++ comb n xs
>>> comb 2 [1,2,3,4,5]
[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]
n種類のものから重複を許してr個選ぶ
>>> import Control.Monad
>>> replicateM 5 ["a", "b", "c"]
[["a","a","a","a","a"],["a","a","a","a","b"],["a","a","a","a","c"],["a","a","a","b","a"],["a","a","a","b","b"],["a","a","a","b","c"],["a","a","a","c","a"],["a","a","a","c","b"],["a","a","a","c","c"],["a","a","b","a","a"],["a","a","b","a","b"],["a","a","b","a","c"],["a","a","b","b","a"],["a","a","b","b","b"],["a","a","b","b","c"]...]
べき集合
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = [x:ps | ps <- powerset xs] ++ powerset xs
または
import Control.Monad
powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs
>>> powerset [1,2,3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
直積
3個の集合の直積。何個でもOK。
>>> import Control.Monad
>>> sequence [[1,2], [3,4], [5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]