How can I obtain all partitions of a list in Mathematica?

Question

By partition of a list, I mean a set of subsets of the list elements such that the intersection of any distinct pair of subsets is empty, and the union of all subsets is equal to the original list.

For example, if my input list is {1,π,x} then I'd like a function that returns

{ {{1},{π},{x}}, {{1,π},{x}}, {{1,x},{π}}, {{1},{x,π}}, {{1,π,x}} }

Answer 1

Using adapted code from 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]]

---

Or, unsurprisingly, the Combinatorica package has this function (SetPartitions) already!

Needs["Combinatorica`"]

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

check that they both return the same result (but in different orders)

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

Answer 2

I would start with a Powerset of the set (use Subsets[x]) and then filter out the ones where Union[x] of the set is not the original set.

A bit slow, but I find it intuitive.