# Partition a set into $k$ non-empty subsets

The Stirling number of the second kind is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. In Mathematica, this is implemented as StirlingS2. How can I enumerate all the sets? Ideally I would like to get a list of lists, where each list contains $k$ lists.

The question Partition a set into subsets of size k seems relevant.

-
Related: (8528) – Mr.Wizard Feb 16 '13 at 1:18

<< Combinatorica
KSetPartitions[{a, b, c}, 2]
(*
{{{a}, {b, c}}, {{a, b}, {c}}, {{a, c}, {b}}}
*)

StirlingS2[3, 2]
(* 3 *)

-
Those who use Cobinatorica on 8 and 9 may be interested in this answer. This is how I usually load it now. – Szabolcs Feb 16 '13 at 2:07
@Szabolcs Oh! Thanks for linking it. All those error msgs are creepy sometimes – Dr. belisarius Feb 16 '13 at 2:23

This is faster than the Combinatorica function:

KSetP[{}, 0] = {{}};
KSetP[s_List, 0] = {};
KSetP[s_List, k_Integer] /; k > Length@s = {};
KSetP[s_List, k_Integer] /; k > 0 :=
Block[{ikf, s1 = s[[1]]},
ikf[set_] := Array[MapAt[#~Prepend~s1 &, set, #] &, Length@set];
Join[
Prepend[#, {s1}] & /@ KSetP[Rest@s, k - 1],
Join @@ ikf /@ KSetP[Rest@s, k]
]
]

(r1 = KSetPartitions[Range@12, 4]) // Timing // First

(r2 = KSetP[Range@12, 4])          // Timing // First

1.529

1.139


The output is in a different order but it is equivalent:

Sort[Sort /@ r1] === Sort[Sort /@ r2]
`

True

-