Haskell中的一組分區

我正在嘗試編寫一個可以返回用戶定義的分區集的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')]。但是，我不確定相當多。我認爲這將需要遞歸，如果這甚至可以適當地適應。這裏是集代碼：Haskell中的一組分區

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

來源

2017-10-05 Matt Robbins

。如果你可以對'X'進行分區，那麼你如何分配'X∪{a}'？ –

小調風格的評論：你發佈的「if」似乎是一種複雜的寫作方式，分別是1）'x == y || isElement x ys'和2）'isElement y xs && subset ys xs'。這裏不需要'做'，'== True'總是多餘的。 – chi

的想法是，爲了找到一套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

來源

2017-10-05 23:46:47

你也可以將'partitions'定義爲'partitions = foldr expand [[]]' – 4castle

僞的一個遞歸算法：

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.

來源

2017-10-06 01:39:04 Davislor

是的，我通常不會寫出看起來像家庭作業問題的完整解決方案，但我會給出提示。 – Davislor

如果我刪除了該評論，你願意嗎？（1）這是一個很酷的想法，（2）已經有一個更簡單的解決方案，其他發佈的答案和（3）我不清楚你的意思。 – Alec

@Alec這真的取決於你。 – Davislor

Haskell中的一組分區

回答

相關問題