Consider a finite set $X$ and the boolean algebra $\mathcal{P}(X)$ of the subsets of $X$. While I focus on $\mathcal{P}(X)$ in this question, the problem could be expressed more generally in any boolean algebra.

I have $n$ elements $P_1,P_2....P_n$ of $\mathcal{P}(X)$. I am interested in the unions of any combination of these elements that I simply write $P_I=\bigcup_{i\in I}P_i$ for any $I\subseteq \{1,2,...,n\}$.

Possibly there could be up to $2^n$ such unions. But I know in my situation that there is a lot of redundancy, and that there are much fewer different unions: there are many combinations $I$ such as $P_I$ is the same.

I want to find the maximal combinations $I$ producing a fixed union: $I$ is such as for all $J\supset I$ we have $P_J\supset P_I$ (inclusion is strict). It is a combination such as any super-combination produces a strictly bigger union. Minimal combinations are also interesting to me, even though the problem is not exactly the same.

Any thought about an algorithmic idea to produce (efficiently) the list of all such combinations?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.