在 Haskell 中划分一组

Question

我正在尝试编写一个 Haskell 程序，该程序可以 return 用户定义集的分区集。集合 S 的划分定义为 S 的一组非空、成对不相交的子集，其并集为 S。因此，[1,2,3] returns [[[2],[3,1]],[[2,1],[3]],[[3,2,1]],[[1],[3,2]],[[1],[2],[3]]]。我想我可以利用我刚才写的一个不同的程序来从两个集合中找到笛卡尔积。所以，[1,2,3] ['a', 'b'] returns [(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 第一。然后以各种可能的方式将 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 构建为尾递归函数的累积参数，或构建为每个步骤的 return 值的并集。正确的子集函数在 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，它returns只有非空真子集的集合S 的，并且每个分区和子分区都是一个集合差异，因此成对不相交。

任何基数为 2 的分区集都具有 {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[=24 的分区集=]-1，在对搜索树的父节点进行子分区时会找到。因此，通过归纳，算法找到了S的所有分区集。

Answer 3

最近又在玩set分区和haskell。尽管它可能不是最快和最好的解决方案，但它可以完成工作。我发现使用 Data.List 和 List Monad 大大减少了代码量并提高了可读性。

问自己是否有一种巧妙的方法可以将 foldl 替换为 foldr？

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

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。

在 Haskell 中划分一组

Partition a set in Haskell

haskell

set

partition