Find all partitions from a list of subsets
-
11-06-2021 - |
Question
Given a list of specific subsets like
S = [ {1, 2}, {3, 4}, {1}, {2, 3}, {4}, {3} ]
and a "universe" set like
U = {1, 2, 3, 4}
what elegant and simple algorithm can be used to find all the possible partitions of U made of sets from S? With this example, such partitions include
{1, 2} {3, 4}
{1, 2} {3} {4}
etc.
Solution
Use recursion.
Split the problem into two smaller problems based on whether the first element is used or not:
- Partition using
{1,2}
and any of the the remaining sets. - Partition without using
{1,2}
but using any of the the remaining sets.
These two options cover all possibilities.
- The first is solved by partitioning
{3,4}
using only[ {3, 4}, {1}, {2, 3}, {4}, {3} ]
. - The second is solved by partitioning
{1,2,3,4}
using only[ {3, 4}, {1}, {2, 3}, {4}, {3} ]
.
To see how to solve these smaller problems refer to this similar question.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow