목록의 가능한 모든 하위 목록

Question

목록의 가능한 모든 하위 목록의 목록을 포함하는 목록을 생성하는 함수를 작성해야합니다.

partitions :: [a] -> [[[a]]] 

그것을 제공한다 : 따라서 유형이어야

파티션 [1..4] = [1], [2], [3], [4] [[1,2], [3], [4]], [[1], [2,3], [4]], [[1,2,3], [4] 1], [2], [3,4]], [[1,2], [3,4]], [[1], [2,3,4]], [[1,2,3 , 4]]]

나는 목록 열람이 최선의 방법이라고 생각하고 있습니다. 지금까지 내가 가지고있는 것 :

partitions :: [a] -> [[[a]]] 
partitions (x:xs) = foldr insert [[]] (x:xs) 
    where insert ys zs = ys:x:zs 

예상대로 유형 오류가 발생하지만이를 수정하는 방법을 모르겠습니다. 나는 명백한 것을 놓치고 있다고 느낀다. 어떤 도움이라도 인정 될 것이다.

Answer 1

직접 재귀로 시작할 것입니다. 그것을 분해하십시오. 긴 목록의 첫 번째 요소에는 어떤 가능성이 있습니까?

1. 파티션 목록 중 하나의 요소 일 수 있습니다.
2. 둘 이상의 요소가있는 파티션 목록의 일부일 수 있습니다. 귀하의 예제에서

, 당신이 순서대로 원래의 요소를 유지하려는 것 같다, 그래서 각 파티션의 회원 만 다소 쉽게 연속 하위 목록이 될 수 있습니다.

그래서 우리는

*Partitions> partitions [1,2,3,4] 
[[[1],[2],[3],[4]],[[1],[2],[3,4]],[[1],[2,3],[4]],[[1],[2,3,4]],[[1,2],[3],[4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4]]] 

하지 원하는 순서를 산출

partitions :: [a] -> [[[a]]] 
partitions [] = [[]] -- only one partition of an empty list, an empty partition 
partitions (x:xs) = [[x]:part | part <- partitions xs] ++ [(x:ys):yss | (ys:yss) <- partitions xs] 

를 시작할 수 있습니다. 그게 중요하다면 우리는 다시 써야합니다. 원하는 순서는 직접 계승의 첫 번째 요소 모두 선택을 나열, 그래서 우리는 쓸 수 그것은 우리가 명시 적으로 비어 있지 않은 파티션합니다 (재귀의 끝에서) 빈 파티션의 경우를 구별 할 필요가

partitions (x:xs) = partitions xs >>= \zs -> case zs of 
               [] -> [[[x]]] 
               (ys:yss) -> [[x]:ys:yss, (x:ys):yss] 

, 위의 패턴은 암시 적으로 패턴 (ys:yss)에 바인딩하여 수행되었습니다. 즉,리스트의 바인드 모나드 (>>=)flip concatMap는,

partitions (x:xs) = concatMap insert (partitions xs) 
    where 
    insert [] = [[[x]]] 
    insert (ys:yss) = [[x]:ys:yss, (x:ys):yss] 

더 읽을 수있는 버전이다는 사실을 이용하여 원하는 순서

*Partitions> partitions [1,2,3,4] 
[[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4]],[[1],[2,3,4]],[[1,2,3,4]]] 

를 산출한다.