在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

- Matt Robbins

---

递归地。如果您可以对X进行分区，那么如何对X∪{a}进行分区？ - n. m.

稍微提一下样式问题：您发布的 if 语句似乎是一个复杂的写法，分别是1)x == y || isElement x ys和2)isElement y xs && subset ys xs。这里不需要使用do，而且== True总是多余的。 - chi

Answer 1

这个想法是为了找到集合X ∪ {x}的所有分区，我们首先找到X的分区。然后以每种可能的方式将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

- n. m.

---

你也可以将 partitions 定义为 partitions = foldr expand [[]]。 - 4castle

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的所有真子集有一个全序关系，则可以使用对称性打破方法，仅添加在排列上唯一的分区。也就是说，如果X>Y，则只能添加{X，Y}而不能添加{Y，X}，只能添加{X，Y，Z}而不能添加{Y，X，Z}。注意，您仍然需要精确地对每个集合进行子分区！

这仅找到S的分区集合，如果⋃Z = X且X∪Y = S，则Z和Y中所有集合的并集是S，它仅返回S的非空真子集的集合，并且每个分区和子分区都是集合差异，因此成对不相交。

任何基数为两个的分区集合都具有{X，S-X}的形式，该算法通过尝试每个可能的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的所有分区集合。

- Davislor

---

是的，我通常不会写完整的解决方案来回答看起来像作业问题的问题，但我会给出一些提示。 - Davislor

你希望我删除那条评论吗？我添加它的原因是：（1）这是一个很酷的想法，（2）其他已发布的答案中已经有了一个更简单的解决方案，（3）我一开始并不清楚你的意思。 - Alec

@Alec 这真的取决于你。 - Davislor

鉴于两个陌生人都同意了您的意见，我已经删除了该评论。 :) - Alec

@Alec 好的，有六个陌生人点赞了另一个完整的解决方案。 - Davislor

Answer 3

最近，我又开始玩集合分割和Haskell了。尽管它可能不是最快和最好的解决方案，但它确实能胜任工作。我发现使用Data.List和List Monad极大地减少了代码量并扩展了可读性。

我在想是否有一种简洁的方法来用foldr替换foldl？

无论如何，这是我的解决方案：

module Main where

import Data.List

main :: IO ()
main = print $ allPart 5

insertFront :: Integer -> [[Integer]] -> [[Integer]]
insertFront k (h:t) = [k:h]++t
insertFront k _ = [[k]]

add :: Integer -> [[Integer]] -> [[[Integer]]]
add k part=zipWith (++) (inits part) (map (insertFront k) (tails part))

allPart k = foldl (>>=) [[]] [add i | i<-[1..k]]

我也在想是否有一些非常短的替代方法，可以使用Haskell库来实现insertFront。

- Aleph0