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

はわわーっ

はわわわわっ

もう少し順列

haskell で順列を列挙するやつ。選んだ要素と残りの要素を両方とも持っておかないといけないので、ペアを使うことにする。

まず、残ってるやつから1つ選ぶ関数を作る。

pickup :: [a] -> [([a], [a])]
pickup xs = [([head s], f ++ tail s) |
             i <- [0..length xs -1], let (f, s) = splitAt i xs]

main :: IO ()
main = do
  print $ pickup "abcde"
[("a","bcde"),("b","acde"),("c","abde"),("d","abce"),("e","abcd")]

fold を使うとこんな感じ。

pickup :: [a] -> [([a], [a])]
pickup = foldr (\x rs ->
               ([x], concatMap fst rs) : (\(as, bs) -> (as, x:bs)) `map` rs) []

で、これを使って順列を求める。

pickup :: [a] -> [([a], [a])]
pickup = foldr (\x rs -> ([x], concatMap fst rs) :
                         map (\(as, bs) -> (as, x:bs)) rs) []

permutations :: Int -> [a] -> [([a], [a])]
permutations 0 xs = [([], xs)]
permutations _ [] = []
permutations n xs = concatMap
                    (\(as, bs) ->
                    map (\(ps, rs) -> (as ++ ps, rs)) $ pickup bs) $
                    permutations (n-1) xs

main :: IO ()
main = do
  print $ length  $ permutations 3 "abcde"
  print $ map fst $ permutations 3 "abcde"
60
["abc","abd","abe", ... ]