I'm having trouble solving this problem efficiently:
Let's say we have the following sets
{1, 2, 3}
{1, 2}
{2, 3}
{1}
We want to eliminate those sets which are supersets of other sets. For example, {1} is a subset of both {1, 2, 3} and {1, 2}, so those two would be eliminated. Likewise, {2, 3} is a subset of {1, 2, 3} so could also eliminate it. After these elimination operations are complete we would be left with the following:
{2, 3}
{1}
It is important to note that the span of the union of all sets doesn't need to be preserved, and should {2, 3} have been replaced with {2}, it also would have eliminated {1, 2, 3}, leaving only {1} and {2}.
For the problem I'm working on I have to find the most reduced sets for 4 billion sets (let's call these sets $S$), where each set in $S$ could contain anywhere from 1 to 32 sets, resulting in a possible 66 billion comparisons.
Is there a way to use mathematics to model these sets to make it more efficient to run?
EDIT
For clarification, the nesting of the sets can be represented as follows:
{
{
{1, 2, 3}
{1, 2}
{2, 3}
{1}
},
{
{1, 2}
{1}
},
...
}
The first nested layer in this representation represents $S$, and the sets within each set in $S$ are represented by second nested layer. In this case these are the sets with numbers in them.
Since you are looking at all $2^{32}$ possible sets of sets of 5 different elements, that means that the end result will be the set of all irreducible sets of sets of those elements: every such an irreducible set will be in the original set, and hence will end up in the resulting set, and every reducible set will reduce to one of those irreducible sets.
So, rather than starting with all 4+ billion sets of sets and doing that crazy number of comparisons, there is in fact no need to go through the actual reductions at all! It is really just a manner of figuring out all those irreducible sets of sets!
Addition
When I say it is 'just' a matter of figuring out all those irreducible sets of sets I do not mean that that is a trivial task ... In fact, coming up with an algorithm that systematically generates all those sets will still require some thinking, and some algorithms to do this will be more efficient than others (indeed, coming up with an efficient algorithm is an interesting problem in and of itself). But, whatever way you come up with, I'm sure it'll be a heck of a lot more efficient than doing the actual reductions!
Addition 2
OK, so here is a sketch of an algorithm I came up with:
Define $SSS(S)$ relative to some set $S$ of elements to be the set of sets of elements occurring in $S$ that contains all the irreducible sets of sets of those elements, with the exception of the empty sets of sets, and the set containing only the empty set. In other words, $SSS(\{0,1,2,3,4\})$ (which I'll abbreviate to $SSS_4$ is what we're eventually after once we include those last two sets. But as it turns out, the more general $SSS(S)$ is handy to work with for the algorithm given any set $S$.
Algorithm:
Start with a set of sets of sets $SSS_0 = \{\{\{0\}\}\}$.
Now loop where for any $n$, create $SSS_{n+1}$ from $SSS_n$ as follows:
A. First, add $\{\{n+1\}\}$ to $SSS_{n+1}$
Then, for each $SS \in SSS_n$:
B. Add $SS \cup \{\{n+1\}\}$ to $SSS_{n+1}$
C. 'Extend' every $S \in SS$ with $n+1$ to form a set $SSS_{S,n+1}$ of sets of sets of elements, take the 'çross-product' of all such generated $SSS_i$, and add the resulting sets to $SSS_{n+1}$.
By 'extending' $S$ with $m$ to form $S_m$ I mean the following operation:
C1. If $S = \{ x \}$ for some single element $x$, then $SSS_{S,m} = \{\{\{x\}\},\{\{x,n\}\}\}$. Add this to final result and stop
C2. If $S$ contains two or more elements, figure out $SSS(S)$.
C3. Remove $\{S\}$ from this set. Call this $SSS1$
C4. Add $m$ to each of the $S' \in SS \in SSS1$. Call this $SSS2$
C5. Add $S$ to each $SS \in SSS2$. Call this $SSS3$
C6. Add $\{S\}$ and $\{ S + m \}$ to $SSS3$ and add all this to final result.
By taking a 'cross-product' $SSS_1 \times SSS_2 \times ... \times SSS_n$ of sets I mean something akin to the Cartesian product: find all tuplets with one element from $SSS_1$, one from $SSS_2$, etc. except that instead of making this into a tuple, the elements should be unioned into one new set. And yes, make sure to regard these as operations on sets, since you can get multiple copies of the same set during this process.
Finally, when you have reached the desired $n$, add $\{\}$ (the empty sets of sets) and $\{\{\}\}$ to $SSS_n$, and that will be set of all irreducible sets of sets of integers $0$ through $n$.
Example:
What is $SSS_2$?
OK, start with $SSS_0 = \{\{\{0\}\}\}$
Then for $SSS_1$ we get:
A. First, add $\{\{1\}\}$
There is only one set $SS \in SSS_0$, and that is $\{\{0\}\}$, so:
B. Add $\{\{0\}\} \cup \{\{1\}\} = \{\{0\},\{1\}\}$ to $SSS_1$
C1. $SSS_{\{0\},1\}} = \{\{\{0\}\},\{\{0,1\}\}\}$.
So: $SSS_1$ = $\{\{\{1\}\},\{\{0\},\{1\}\},\{\{0\}\},\{\{0,1\}\}\}$
Moving on to $SSS_2$:
A. Add $\{\{2\}\}$
B. Adding $\{2\}$ to all $SS \in SSS$, we get $\{\{1\},\{2\}\}$, $\{\{0\},\{1\},\{2\}\}$, $\{\{0\},\{2\}\}$, and $\{\{0,1\},\{2\}\}$.
C.
Extending $\{0\}$ with $2$ we get $\{\{\{0\}\},\{\{0,2\}\}\}$.
Likewise, extending $\{1\}$ with $2$ we get $\{\{\{1\}\},\{\{1,2\}\}\}$.
For $\{\{0\},\{1\}\}$ we take the cross-product of $\{\{\{0\}\},\{\{0,2\}\}\}$ and $\{\{\{1\}\},\{\{1,2\}\}\}$, giving us: $\{\{0\},\{1\}\}$, $\{\{0,2\},\{1\}\}$, $\{\{0\},\{1,2\}\}$, and $\{\{0,2\},\{1,2\}\}$
Finally, for $\{\{0,1\}\}$ we get:
C2. $SSS(\{0,1\}) = \{\{\{1\}\},\{\{0\},\{1\}\},\{\{0\}\},\{\{0,1\}\}\}$
C3. Remove $\{\{0,1\}\}$ so we get $\{\{\{1\}\},\{\{0\},\{1\}\},\{\{0\}\}\}$
C4. Add $2$ to all sets: $\{\{\{1,2\}\},\{\{0,2\},\{1,2\}\},\{\{0,2\}\}\}$
C5. Add $\{0,1\}$ to all sets of sets: $\{\{\{0,1\},\{1,2\}\},\{\{0,1\},\{0,2\},\{1,2\}\},\{\{0,1\},\{0,2\}\}\}$
C6. Finally, add $\{\{0,1\}\}$ and $\{\{0,1,2\}\}$
Putting all these together, we get:
$SSS_2 = \{\{\{2\}\},\{\{1\},\{2\}\},\{\{0\},\{1\},\{2\}\}, \{\{0\},\{2\}\},\{\{0,1\},\{2\}\},\{\{0\}\}, \{\{0,2\}\},\{\{1\}\},\{\{1,2\}\}, \{\{0\},\{1\}\}, \{\{0,2\},\{1\}\}, \{\{0\},\{1,2\}\}, \{\{0,1\},\{1,2\}\},\{\{0,1\},\{0,2\},\{1,2\}\},\{\{0,1\},\{0,2\}\},\{\{0,1\}\}, \{\{0,1,2\}\} \}$
OK, two more iterations, and you have $SSS_4$, and then add $\{\}$ and $\{\{\}\}$ to that to get your desired set. That's it!