7
$\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$
1
  • 1
    $\begingroup$ Related: (8528) $\endgroup$
    – Mr.Wizard
    Feb 16, 2013 at 1:18

2 Answers 2

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

 StirlingS2[3, 2]
 (* 3 *)
$\endgroup$
2
  • 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, 2013 at 2:07
  • 1
    $\begingroup$ @Szabolcs Oh! Thanks for linking it. All those error msgs are creepy sometimes $\endgroup$ Feb 16, 2013 at 2:23
10
$\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$
2
  • $\begingroup$ I think r1 = KSetPartitions needs to be renamed, as my output does not recognise the name? $\endgroup$
    – apg
    May 21, 2019 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, 2019 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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