2
$\begingroup$

Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in each of $S_i$, i.e., for

$S_1$ = $\{sub_11,sub_12,sub_13\}$, where $sub_11$, $sub_12$, $sub_13$ are disjoint,

$S_2$ = $\{sub_21,sub_22\}$, where $sub_21$, $sub_22$ are disjoint

Then find $A$ = $\{asub1,asub2,asub3\}$, where $asub1$, $asub2$ are disjoint

and

$asub1$ can be a subset of only one of $sub_11$ or $sub_12$ or $sub_13$ but not more than one of them. Same goes for $asub2$ and $asub3$.

Similarly

$asub1$ can be a subset of only of either $sub_21$ or $sub_22$ or but not both of them. Same goes for $asub2$ and $asub3$.

More formally,

$\forall sub_i \in S_i,$ and given a subset $asub \in A,$

If $Asub=\{sub_i\mid asub\subseteq sub_i\}$

$then$ $|Asub|=1$

$Example 1:$

$X = \{e1,e2,e3,e4,e5\}$

$S_1 = \{\{e1,e2\},\{e3,e4\},\{e5\}\}$

$S_2 = \{\{e1\},\{e2,e3,e4\},\{e5\}\}$

$S_3 = \{\{e1,e2,e3,e4\},\{e5\}\}$

$A= \{\{e1\},\{e2\},\{e3,e4\},\{e5\}\}$

$Example 2:$

$X = \{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12\}$ $S_1 = \{\{e1,e2,e11,e12\},\{e3,e4,e5,e6\},\{e7,e8,e9,e10\}\}$ $S_2 = \{\{e1,e2,e3\},\{e4,e5,e6,e7,e8\},\{e9,e10,e11\},\{e12\}\}$

$A= \{\{e1,e2\},\{e3\},\{e4,e5,e6\},\{e7,e8\},\{e9,e10\},\{e11\},\{e12\}\}$

Preferably the algorithm for finding $A$ should take optimal time.

P.S. Forgive me if the mathematical description of the problem is not formal enough or if there are mistakes in it, I am not a mathematician.

$\endgroup$
0
$\begingroup$

Without loss of generality, each asub$i$ can be taken to have exactly one element (size 1). (If there is any solution, then there is a solution where all asub$i$'s are of size 1.)

Now it's easy to iterate over all sets of size 1 and determine which are valid for asub$i$. Let $A$ be the collection of all such sets. There is your solution. As a bonus, I even gave you a solution where $A$ is as large as possible.

The running time is polynomial (in fact, quadratic), so this should be an efficient algorithm.

$\endgroup$
  • $\begingroup$ can you illustrate this algorithm using an example, that would be useful. $\endgroup$ – themanwhosoldtheworld Jan 7 '18 at 4:40

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.