読者です 読者をやめる 読者になる 読者になる

はわわーっ

はわわわわっ

haskell で順列とか組み合わせとか

haskell

Data.List に permutations ってのがあるけど、P(n, k) 的なものとか組み合わせはないので作ってみた。

まず、permutations を使ってみる。

import Data.List

main = do
  print $ permutations "abcd"
  print $ length $ permutations "abcd"
["abcd","bacd","cbad", ... ]
24

で、組み合わせを作ってみる。@fumieval さんに教えてもらった。

combinationsN :: Int -> [a] -> [[a]]
combinationsN 0 _      = [[]]
combinationsN _ []     = []
combinationsN n (x:xs) = (x:) `map` (combinationsN (n-1) xs) ++ combinationsN n xs

main :: IO()
main = do
  print $ combinationsN 3 "abcdef"
  print $ length $ combinationsN 3 "abcdef"
["abc","abd","abe", ... ]
20

あるいは Data.List の sequences を使うと

import Data.List

combinationsN :: Int -> [a] -> [[a]]
combinationsN n = filter ((== n) . length) . subsequences

main :: IO()
main = do
  print $ combinationsN 3 "abcdef"
  print $ length $ combinationsN 3 "abcdef"

こんな感じにかける。
で、最後に n個からk個取り出す順列 P(n, k) を列挙するようなもの。
combinationsN で組み合わせを選んでから permutations を使う。

import Data.List

combinationsN :: Int -> [a] -> [[a]]
combinationsN n = filter ((== n) . length) . subsequences

permutationsN :: Int -> [a] -> [[a]]
permutationsN n = concatMap permutations . combinationsN n

main :: IO()
main = do
  print $ permutationsN 3 "abcdef"
  print $ length $ permutationsN 3 "abcdef"
["abc","bac","cba", ... ]
120

効率がどうとかよくわかってないけど、とりあえず動くのでいいことにする。