Why not login to Qiita and try out its useful features?

We'll deliver articles that match you.

You can read useful information later.

9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-02-17

順列

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Advent Calendar is held!

Qiita Advent Calendar is an article posting event where you post articles by filling a calendar 🎅

Some calendars come with gifts and some gifts are drawn from all calendars 👀

Please tie the article to your calendar and let's enjoy Christmas together!

9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?