Haskell 順列・組み合わせ・べき集合・直積

順列

>>> 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]]