順列組み合わせの生成

Haskell

重複、省略のない順列を返す関数を書いてみました。なんだか、もっと簡単にかけそうな気がするのですが、さっぱりといきません…Preludeとかにあっても驚かない気もするのですが、見つかりませんでした。

順列生成の元となる要素集合をリスト[a]で与えて、そこから生成される順列をaで帰すという形にします。
permutation :: [a] -> [ [a] ]

そして、次のような結果を返したいわけです...
permutation [1, 2, 3] = [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]

僕が最初にひねり出したのはこんな感じ...なんだかやたらと＋＋が使われたコードになりました。

module Main
	where

{- skipOnes [1, 2, 3] = [(1, [2, 3]), (2, [1, 3]), (3, [1, 2])] -}
skipOnes :: [a] -> [(a, [a])]
skipOnes xs = _skipOne [ ] xs
  where
    _skipOne :: [a] -> [a] -> [(a, [a])]
    _skipOne _ [ ] = [ ]
    _skipOne xs (y:ys) = (y, xs ++ ys) : _skipOne (xs ++ [y]) ys

permutation1:: [a] -> [ [a] ]
permutation1 xs = _permutation [ ] xs
  where
    _permutation :: [a] -> [a] -> [ [a] ]
    _permutation xs [ ] = [xs]
    _permutation xs ys = do 
      (y, yss) <- skipOnes ys
      _permutation (xs ++ [y]) yss

main = print $ permutation1 [1..3]
	

    

  • > [ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
    •

これを書くときに気をつけたのが、リストのトラバースの回数をできるだけ減らすことだったのですが、その分リストの編集が増えているような気がします...うーんと思って、Data.Listを眺めていたら、deleteという関数を発見：
delete :: (Eq a) => a -> [a] -> [a]

delete 3 [1..3] = [1, 2]
これとリストコンプリヘンションを使えば、最初のバージョンと似たような方針のコードがもうちょっと簡単に書けそうです…
それで出来上がったのが、これ：

module Main where

import Data.List

permutation2 :: (Eq a) => [a] -> [ [a] ]
permutation2 [ ] = [ [ ] ]
permutation2 xs =
    [z | x <- xs, z <- map (x:) (permutation2 (delete x xs))]

main = print $ permutation2 [1..3]

もう一歩進めて、リストコンプリヘンションのところをリストのモナド的表記に変えると：

permutation :: (Eq a) => [a] -> [ [a] ]
permutation [ ] = [ [ ] ]
permutation xs = 
  xs >>= \x -> map (x:) $ permutation $ delete x xs

ずいぶんとシンプルになりました。しかしながら、両方とも、要素数が10を越えるリストを入力にするとずいぶんと遅くなります。まぁn!個だけのリストを生成する関数なので、早くやれというのも無理があるのかもしれません。つまり、こんな関数を使うぐらいなら、何かほかのやり方を考えたほうが良いということなのかもしれません...Preludeにない理由もわかる気がする？