0

I have a set of elements A = {a, b, c, d, e, f}

I want to get all sets of disjoint sets of any size that cover A. So {{{a,b}, {c,d,e,f}}, {{a,b}{c,d,e}{f}}, {{a,b,c}{d,e,f}}...}, etc.

Is there an easy (not too slow) way of doing this? Ideally in python, but the general algorithm would also be appreciated.

I tried getting the power-set of the power-set to then filter out the sets with disjoint sets, but that blows up too quickly and kills my computer.

The purpose is to find all possible subtrees in a tree make make up that tree again.

lebelinoz
  • 4,890
  • 10
  • 33
  • 56
Matías Guzmán Naranjo
  • 495
  • 1
  • 4
  • 16
  • "but that blows-up too quickly and kills my computer." - The size of the set you are attempting to construct is exponential, for the power set is a subset of your set. So, it is not clear what you mean by "easy (not too slow) way of doing this" – Tryer Oct 05 '17 at 16:58
  • Does {{a,c,e},{b,d,f}} count? – Matt Timmermans Oct 05 '17 at 17:30
  • You're looking to generate all partitions of the set. Here's a previous [question](https://stackoverflow.com/questions/20530128/how-to-find-all-partitions-of-a-set) that addresses this problem: – RaffleBuffle Oct 05 '17 at 19:07
  • Possible duplicate of [How to find all partitions of a set](https://stackoverflow.com/questions/20530128/how-to-find-all-partitions-of-a-set) – Antimony Oct 05 '17 at 21:44

0 Answers0