Haskellで組合せ

　順列ができれば、組合せもできます。
　リストから、m 個だけ取り出す組合せ。
　組合せでは、順列のうち、並べ替えても同じにならないものだけを取り出します。

　つまり、いったん順列を考えて、そのうち最初のm個だけ取り出す。
　さらに、ここから並べ替えて同じになるものを取り除けばいいわけですね。

　ところで、並べ替えて同じになるかどうか調べるのだったら、昇順(小さいものからの順番)に並べておいて、同じでないものだけを残せばいい。

　ということで、次のようにすれば、順列から組合せができますね。

combination m as = unique [x | x <- map (take m) (permutation as), ascendingOrder x]
  where 
    unique xs = unique' [] xs
      where unique' ys [] = ys
            unique' ys (x:xs) | x `elem` ys = unique' ys xs
                              | otherwise   = unique' (ys ++ [x]) xs
    ascendingOrder []  = True
    ascendingOrder [x] = True
    ascendingOrder (x:xs) | x <= minimum xs = ascendingOrder xs
                          | otherwise       = False

　実行してみる。1から4までのリストで3つ取り出す組合せは？

Main> combination 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

　1から5まででは？

Main> combination 3 [1..5]
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]
]

　1から6は？

Main> combination 3 [1..6]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[1,5,6]
,[2,3,4],[2,3,5],[2,3,6],[2,4,5],[2,4,6],[2,5,6],[3,4,5],[3,4,6],[3,5,6],[4,5,6]
]
Main>

　でもねえ。
　リストが[1..7]になるとすぐには答えが返ってこなくなって、[1..8]ならなんとか計算結果が得られますけど、リストがそれ以上長くなると、あっけなくエラーになりました。

ERROR - Garbage collection fails to reclaim sufficient space

　おやおや。