As Hevert emphasized, this problem is NP-hard, so there is no effective way to do this. However, if your entry is relatively small, you can still disable it. After all, exponentiality does not mean impossibility. It is simple that exponential problems become impractical very quickly, as the size of the input data grows. But for something like 25 sets, you can easily overdo it.
Here is one approach. Say you have n subsets called S0, S1, ... etc. We can try each combination of subsets and choose one with maximum power. There are only 2 ^ 25 = 33554432 options, so this is probably reasonably reasonable.
An easy way to do this is to notice that any non-negative number, strictly below 2 ^ N, is a certain choice of subsets. Look at the binary representation of a number and select the sets whose indices correspond to the bits that are included. So, if the number is 11, then 0, 1, 3 digits are included, and this corresponds to the combination [S0, S1, S3]. Then you just make sure that these three sets do not actually intersect.
Your procedure is as follows:
- Iteration I 0 to 2 ^ N - 1
- For each value, I use the bits that are included to determine the appropriate combination of subsets.
- If these subsets do not overlap in pairs, update your best answer with this combination (i.e. use this if it is larger than your current one).
Alternatively, use backtracking to generate your subsets. These two approaches are equivalent, modulo the implementation of compromises. A rollback may have some kind of overhead stack, but it may cut off entire lines of computation if you check for disjointness along the way. For example, if S1 and S2 are not disjoint, then he will never worry about any larger combinations containing the two, saving some time. The iterative method cannot optimize itself in this way, but is fast and efficient due to bitwise operations and a tight loop.
The only non-trivial thing here is to check if the subsets fall into pairs that are disjoint. There are all kinds of tricks that you can pull out here, depending on the limitations.
A simple approach is to start with an empty set structure (select everything you want from your chosen language) and add elements from each subset one at a time. If you have ever hit an element that is already installed in a set, then it occurs in at least two subsets, and you can refuse this combination.
If the original set S has m elements and m is relatively small, you can map each of them to the range [0, m-1] and use bitmasks for each set. Therefore, if m <= 64, you can use Java long to represent each subset. Include all the bits corresponding to the elements in the subset. This allows you to quickly start the specified mode due to the speed of bitwise operations. A bitwise AND corresponds to a given intersection, and a bitwise AND corresponds to a union. You can check if two subsets are intersecting by seeing that the intersection is empty (i.e. USING two bit masks gives you 0).
If you have few such elements, you can still avoid repeating multiple intersections several times. You have very few sets, so precommute which ones don't intersect at the beginning. You can simply save a Boolean matrix D such that D [i] [j] = true if i and j do not intersect. Then you simply look at all the pairs in combination to check for pairwise disjointness, and do not perform real dialing operations.