Enumerate subsets that intersect each subset in a fixed family

56 Views Asked by At

Let $\Omega=\{1,\dots,n\}$ and let $A_i\subset \Omega$, $1\leq i\leq m$ be a fixed family of subsets of $\Omega$.

Let $$ \mathcal{A}:=\{B\subset \Omega: B\cap A_i \neq \varnothing \;\forall 1\leq i\leq m\}. $$

Is there an efficient way to enumerate $\mathcal{A}$ in any order that is compatible with the cardinality partial order, i.e. find $B_j\in\mathcal{A}$, $1\leq j\leq L$ such that $|B_j|\leq |B_{j+1}|$ and $\mathcal{A}=\{B_1,...,B_L\}$?

Of course I can always just enumerate all subsets of $\Omega$ in a way that respects the cardinality order and check for each subset whether it is in $\mathcal{A}$. However, this can be rather inefficient. For example, if $A_{i}=\{i\}$, $1\leq i\leq m=n$, then $\mathcal{A}=\{\Omega\}$ but obtaining that single element of $\mathcal{A}$ would take $2^n$ steps.

PS: The specific order of the $B_j$ is not important, but it would be nice if the order did not depend on $\mathcal{A}$. In other words, I want to apply the same algorithm to another scenario with $\tilde{A}_i$ such that the corresponding $\tilde{B}_j$ are ordered in the same way. However, this is not a strict requirement, I'm sure I will find a workaround.