2
$\begingroup$

I would like to write an efficient code for splitting a set into k disjoint subsets, whose union would be the input set. The input set is represented by sorted lists with no repetitions, and the resulting sets are also expected in this form. For example ListCompositions[{a,b,c,d},2]

produces

{{},{a,b,c,d}}, {{a},{b,c,d}}, {{b},{a,c,d}}, {{c},{a,b,d}}, {{d},{a,b,c}}, {{a,b},{c,d}}, {{a,c},{b,d}}, {{a,d},{b,c}}

I know that Mathematica is not an optimal tool for this type of problems, but the code won't be used for gigantic sets.

EDIT: I'm now aware of KSetPartitions function, but it does not solve the problem completely since it produces only partitions with no empty sets. Thus, the partitions like {{},{a,b,c,d}} from the original example are not obtained.

$\endgroup$
5
  • 7
    $\begingroup$ seen ResourceFunction["KSetPartitions"]: link? $\endgroup$
    – kglr
    Feb 2, 2023 at 13:08
  • $\begingroup$ in addition to @kglr there's also SetPartitions[myList] with myList={a,b,c,d} $\endgroup$
    – bmf
    Feb 2, 2023 at 13:22
  • $\begingroup$ another would be Internal ``PartitionRagged[myList, #] & /@ Apply[Join, Permutations /@ IntegerPartitions[Length[myList]]] $\endgroup$
    – bmf
    Feb 2, 2023 at 13:27
  • $\begingroup$ @wedelfach you say ResourceFunction["KSetPartitions"][yourlist, 2] gives all you need, except that is missing the one solution { {}, yourlist }? Woudn't be trivial to just add that one missing case? $\endgroup$
    – rhermans
    Feb 17, 2023 at 11:51
  • $\begingroup$ Right, it is indeed trivial in this case, but when it gets to Length[list]>k>2 a bit more effort is necessary. I have solved it using auxiliary elements which are added to the list, and the removed, from the partitions. $\endgroup$
    – wedelfach
    Feb 17, 2023 at 12:28

1 Answer 1

1
$\begingroup$
yourList = (Indexed[x, #1] & ) /@ Range[5]
Flatten[(ResourceFunction["KSetPartitions"][
      Append[yourList, \[CapitalPhi]], #1] /. \[CapitalPhi] -> Nothing & ) /@ 
   Range[4], 1]

The output gets big fast!

$\endgroup$

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.