하스켈에서 조합 구현하기

하스켈 연습문제

주어진 리스트에서 중복되지 않은 모든 부분집합을 만들어라.

주어진 리스트에서 n 개를 비복원추출한 조합은 다음과 같이 만든다.

combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations n xs = [ xs !! i : x | i <- [0..(length xs)-1],
                                    x <- combinations (n-1) (drop (i+1) xs)]

> combinations 2 [1..4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

n 개짜리 원소의 리스트의 모든 부분집합은 따라서 다음과 같이 구한다.

combinationAll xs = concatMap (\n -> combinations n xs) [0..length xs]

tails 함수를 이용하기

tails 함수는 앞에서부터 원소를 하나씩 제거한 부분집합을 만들어 낸다.

--   >:m Data.List
--   > tails [0,1,2,3]
--   [[0,1,2,3],[1,2,3],[2,3],[3],[]]

이를 이용해서 다음과 같이 정의할 수 있다.

import Data.List (tails)
combinationsAll xs = concatMap (\n -> combinations n xs) [0..length xs]
where
    combinations 0 _ = [[]]
    combinations n xs = [ y:ys | (y:xs') <- tails xs, ys <- combinations (n-1) xs']