하스켈에서 조합 구현하기
하스켈 연습문제
주어진 리스트에서 중복되지 않은 모든 부분집합을 만들어라.
주어진 리스트에서 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']