6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$
<< Combinatorica`
KSetPartitions[{a, b, c}, 2]
(*
  {{{a}, {b, c}}, {{a, b}, {c}}, {{a, c}, {b}}}
*)

 StirlingS2[3, 2]
 (* 3 *)
$\endgroup$
  • 3
    $\begingroup$ Those who use Cobinatorica on 8 and 9 may be interested in this answer. This is how I usually load it now. $\endgroup$ – Szabolcs Feb 16 '13 at 2:07
  • 1
    $\begingroup$ @Szabolcs Oh! Thanks for linking it. All those error msgs are creepy sometimes $\endgroup$ – Dr. belisarius Feb 16 '13 at 2:23
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think r1 = KSetPartitions needs to be renamed, as my output does not recognise the name? $\endgroup$ – Alexander Kartun-Giles May 21 at 15:36
  • 1
    $\begingroup$ @AlexanderKartun-Giles Sorry, I forgot to include Needs["Combinatorica`"] in my code; if you load that package first does the comparison work as expected? $\endgroup$ – Mr.Wizard May 24 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.