algorithm - 如何找到给定列表的分区？

Question

如何找到整数列表的所有分区？大多数情况下，我需要使用递归的算法，因为我将在 SML 中实现它。我只需要算法，我会自己做编码部分。我错误地编写了查找子集的代码，我没有太多时间来做这个

SML 有点类似于帕斯卡，所以你会掌握我要在阶乘中编写的格式，例如这个有趣的 fuc x = if x<0 then 0 else if x=1 then 1 else x*(fac x-1)

提前致谢

Answer 1

从您对 amit 的回复来看，您似乎在寻找：

fun partitions [] = []
  | partitions [x] = [[[x]]]
  | partitions (x::xs) =
    let
       val zsss = partitions xs
    in
       map (fn zss => [x]::zss) zsss @
       map (fn zs::zss => (x::zs)::zss) zsss
    end

编辑：对不起，我将您之前的示例误读为partition [1,2,3] = [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[1],[2],[3]]]，即有序分区。

这是您实际问题的解决方案（我认为）：

fun extensions x [] = []
  | extensions x (xs::xss) =
    ((x::xs)::xss) :: map (fn zss => xs::zss) (extensions x xss)

fun partitions [] = [[]]
  | partitions (x::xs) =
    List.concat (map (fn zss => ([x]::zss) :: extensions x zss) (partitions xs))

Answer 2

分区问题是一个已知的NP-Hard问题（因此没有已知的多项式解决方案），可以使用用递归很好地编写的穷举搜索来解决。

伪代码（尝试做类似ML的伪代码，希望对您有所帮助和清晰）：

partition([],A,B): #base clause
   if (sum(A) == sum(B)):
        print (A,B) # this is a partition
partition(list, A,B):
   e <- head(list)
   partition(tail(list),e :: A,B)
   partition(tail(list),A, e :: B)

（如果我没记错e :: A是A在 ML 的开头添加一个元素，如果我记错了，请随时更正）

Answer 3

如果你有一个集合的 k 分区，比如说，你可以生成的 k 分区：S {S1,...,Sn}{P1,...,Pk}kS ⋃ {Sn+1}

{P1,..., Pi-1, Pi ⋃ {n+1}, Pi+1,... Pk}对于i{1...k}

加上 (k+1) 分区P ⋃ {k+1}

将这些称为从 生成的分区P。很容易证明，从 的两个不同分区生成的所有分区集{1,...,n}都是不相交的，并且 的每个分区{1,...,n+1}都是从 的某个分区生成的{1,...,n}。

我认为这足以使问题的递归解决方案显而易见。

B(n)为了验证，{1,...,n} 的分区数的计数B是贝尔数，（Sloane A000110）

Answer 4

检查这个找到所有的子集。基本上在每次排列迭代中，您可以通过从当前子集的并集中减去整个集合来获得分区的另一部分。