Haskell中的一組分區

Question

我正在嘗試編寫一個可以返回用戶定義的分區集的Haskell程序。集合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或列表理解來完成這些步驟。您也可以將R作爲累積參數構建到尾遞歸函數，或作爲每個步驟的返回值的並集。正確的子集函數在Haskell標準庫中爲Data.List.subsequences。

如果您對S的所有適當子集都進行了總排序，則可以使用symmetry-breaking來僅添加排列中唯一的分區。也就是說，如果X> Y，則只能添加{X，Y}而不是{Y，X}，只能添加{X，Y，Z}而不能添加{Y，X，Z}。請注意，您仍然將分區中的每個組合分割一次！

這隻能找到S的分區集合，如果Z = X且X∪Y= S，Z和Y中所有集合的並集都是S，它只返回S的非空適當子集的集合，並且每個分區子分配是一個集合差異，因此兩兩不相交。

基數2的任何分區集的格式爲{X，SX}，算法找到它是因爲它會嘗試每個可能的X.任何分區集基數i> 2的格式爲{a_1，a_2，...。 ...，a_i}，其中{a_1，a_2}是{a_1⋃a_2}和{{a_1⋃a_2}，...，a_i}的分區集合，是基數i -1的分區集合，在子分區搜索樹的父節點時找到。因此，通過歸納法，該算法遞歸地查找所有分區集合S.