I have a problem that might be a well-known/researched issue in mathematics and set-theory.
Basically I want to efficiently combine pairs of sets into one single sets, and keep doing that (with an additional constraint that I will explain in my example). I'm trying to come up with an efficient algorithm to implement.
Example:
Let's say I start with five one-element sets: {a}, {b}, {c}, {d}, {e}. I run my constraint/condition test, which will tell me which set(s) I will keep and which set(s) I will remove.
Think of it like that: myConstraint({a}) = Yes (meaning I will keep) or No (meaning I will delete).
Let's assume that after running my constraint I am left with:
{a}, {b}, {c}, {e}: Set 1. ({d} did not satisfy my constraint).
Now I want to form pairs from the sets that I already have, which will give me:
{a, b}, {a, c}, {a, e}, {b, c}, {b, e}, {c, e}
- I can simply do that by starting from first set {a} and pair it with the remaining sets {b}, {c}, and {e}, then go the second set {b} and pair it with the remaining sets {c} and {e}, and finally go to the third set {c} and pair it with the remaining set {e}. - Let's call this Method 1
I run my 'myConstraint' on each set and let's say I'm left with:
{a, b}, {a, c}, {b, c}, {b, e}, {c, e}: Set 2. ({a, e} did not satisfy my constraint)
The total sets that satisfy my constraint are the following (Set 1 + Set 2):
{a}, {b}, {c}, {e}, {a, b}, {a, c}, {b, c}, {b, e}, {c, e}
Now I want to form pairs from those sets. The problem is that if I follow Method 1, I will have many duplicates and duplicates are inefficient to detect; will need to check all previous sets if there's a duplicate)
Here's a sample result for using Method 1
{a, b}, {a, c}, {a, e}, {a, a, b} = {a, b} (duplicate), {a, a, c} = {a, c} (duplicate) . . .: Set3
And finally, I will need to get $Set 1 \cup Set3$ Some duplicates in last step too.
I thought of a couple of algorithms by finding mutually exclusive sets, but I always end up with many duplicates. Is there a neat way to solve this problem?