하스켈에서 파티션 나누기

Question

사용자 정의 집합의 파티션 집합을 반환 할 수있는 하스켈 프로그램을 작성하려고합니다. 집합 S의 분할은 S의 공집합이 S가 아닌 비어 있지 않은 쌍으로 분리 된 집합으로 정의됩니다. 따라서 [1,2,3]은 [[[2],[3,1]],[[2,1],[3]],[[3,2,1]],[[1],[3,2]],[[1],[2],[3]]]을 반환합니다. 나는 전에 내가 쓴 다른 프로그램을 활용하여 두 세트의 데카르트 제품을 발견 할 수 있다고 생각합니다. 따라서 [1,2,3] ['a', 'b']은 [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]을 반환합니다. 그러나, 나는 꽤 어떻게 확신하지 못합니다. 나는 이것이 재 적응을 필요로한다고 생각한다. 여기에 일부 코드 :

type Set a = [a] 

isElement :: Eq a => a -> [a] -> Bool 
isElement x [] = False 
isElement x (y:ys) = if(x==y) then True else isElement x ys 

subset :: Eq a => Set a -> Set a -> Bool 
subset [] xs = True 
subset (y:ys) xs = if(isElement y xs == True) 
        then do subset ys xs 
        else do False 

Answer 1

아이디어는 위해 X ∪ 세트 의 모든 파티션을 찾을 수 있다는 것입니다 {X}는, 우리는 먼저 X의 parritions을 찾을 수 있습니다. 그런 다음 각각의 가능한 방법으로 각각 x을 추가하십시오 (즉, x을 파티션의 첫 번째 요소에 추가하고 x을 두 번째 요소에 추가하는 등). 결과의 합집합을 취하십시오.

이

partitions :: [a] -> [[[a]]] 
partitions [] = [[]] 
partitions (x:xs) = expand x $ partitions xs where 

    expand :: a -> [[[a]]] -> [[[a]]] 
    expand x ys = concatMap (extend x) ys 

    extend :: a -> [[a]] -> [[[a]]] 
    extend x [] = [[[x]]] 
    extend x (y:ys) = ((x:y):ys) : map (y:) (extend x ys) 

데모 : 이 의사 코드 하나의 재귀 알고리즘 https://ideone.com/ClYOoQ

Answer 2

: 이후

If |S| = 1 
    Return ∅ 
Otherwise 
    For each nonempty proper subset X ⊂ S 
    Let Y = S - X 
    Add {X, Y} to R 
    For each Z in {partitionSet(X)} 
     Add Z ∪ {Y} to R. 
    Return R 

목록에 요소 "를 추가하는 것은"는 아닙니다

는 여기에 오히려 간단한 구현입니다 매우 기능적인 관용구라면 concatMap 또는 목록 이해력으로 이러한 단계를 수행하고자 할 것입니다. tail-recursive 함수에 대한 누적 매개 변수 또는 각 단계의 리턴 값의 합집합으로서 R을 빌드 할 수도 있습니다. 적절한 부분 집합 함수는 Haskell 표준 라이브러리에 Data.List.subsequences입니다.

S의 모든 적절한 하위 집합에 대한 전체 순서가있는 경우 대칭 분할을 사용하여 순열까지 고유 한 분할 영역 만 추가 할 수 있습니다. 즉, X> Y 인 경우 {Y, X, Z}가 아닌 {Y, X} 및 {X, Y, Z} 만 추가 할 수 있습니다. 파티션의 모든 세트를 정확히 한 번 하위 파티션으로 조심하십시오!

⋃Z = X 및 X ∪Y = S 인 경우 Z와 Y의 모든 집합의 합집합을 S라고하면 S의 비어 있지 않은 적절한 하위 집합 만 반환하고 모든 하위 집합 하위 분할은 집합의 차이이므로 쌍으로 분리됩니다. ,

카디널리티 두 파티션의 집합 형태 {X, SX}을 가지며,이 모든 가능한 X.에게 카디널리티 I> (2)의 파티션 설정하려고 형태 {A_1, A_2 있기 때문에 알고리즘을 찾는다. .., a_i}는 {a_1 ⋃ a_2}, {a_1 ⋃ a_2}, ..., a_i}의 파티션 집합이며, 카디널리티 집합 i -1이며, 탐색 트리의 부모 노드를 서브 파티셔닝 할 때 발견 될 수있다. 따라서, 유도에 의해, 알고리즘은 S.의 모든 파티션 세트를 찾는다.