如何在Mathematica中获取列表的所有分区？

Question

通过列表的分区,我的意思是一组列表元素,使得任何一对不同的子集的交集是空的,并且所有子集的并集是等于原始列表的子集.

例如,如果我的输入列表是,{1,?,x}那么我想要一个返回的函数

{ {{1},{?},{x}}, {{1,?},{x}}, {{1,x},{?}}, {{1},{x,?}}, {{1,?,x}} }

Answer 1

使用来自http://mathforum.org/advanced/robertd/bell.html的改编代码

BellList[1] = {{{1}}};
BellList[n_Integer?Positive] := Join @@
  (ReplaceList[#,
    {{b___, {S__}, a___} :> {b, {S, n}, a},
     {S__} :> {S, {n}}}
   ] & /@ BellList[n - 1])

s = {a, b, c, d, e};

bell = BellList@Length@s /. n_Integer :> s[[n]]

或者,不出所料,Combinatorica包已经具有此功能(SetPartitions)!

Needs["Combinatorica`"]

comb = SetPartitions[{a, b, c, d, e}]

检查它们是否都返回相同的结果(但是以不同的顺序)

Complement[bell, comb] == {}
Sort@bell == Sort@comb
(* Both of the above return True *)