tjgquicken
asked on
Set theory algorithm question
I'm trying to find a relatively efficient algorithm to solve the following problem:
I have a finite set S = {s_1, s_2, s_3,...}, where each s_i is itself a non-empty finite set. I need to find a subset of S -- call it T -- where the number of elements in the union over all elements in T is equal to the number of elements in T itself.
For example, if I have the set S = {{1,2,8}, {3,5}, {1,3,8}, {2,5,7}, {1,2,5,8}, {3,8}, {2,7}, {7}}, then the algorithm should return the set T = {{3,5}, {2,5,7}, {2,7}, {7}} because T has 4 elements and union({3,5}, {2,5,7}, {2,7}, {7}) also has 4 elements.
The only way I can think of solving this problem is examining each element of the power set of S to see if it matches the criteria, but that algorithm runs in exponential time. Can anybody think of a more efficient way to solve this problem, or point me in the right direction? Thanks.
I have a finite set S = {s_1, s_2, s_3,...}, where each s_i is itself a non-empty finite set. I need to find a subset of S -- call it T -- where the number of elements in the union over all elements in T is equal to the number of elements in T itself.
For example, if I have the set S = {{1,2,8}, {3,5}, {1,3,8}, {2,5,7}, {1,2,5,8}, {3,8}, {2,7}, {7}}, then the algorithm should return the set T = {{3,5}, {2,5,7}, {2,7}, {7}} because T has 4 elements and union({3,5}, {2,5,7}, {2,7}, {7}) also has 4 elements.
The only way I can think of solving this problem is examining each element of the power set of S to see if it matches the criteria, but that algorithm runs in exponential time. Can anybody think of a more efficient way to solve this problem, or point me in the right direction? Thanks.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
... thinking about it. Just curious, what is the motivation for solving the problem? Where the S has got the content? Is it just a theoretical work or does it solve a real problem? Possibly the chance is to approach the solution from a different direction.
Can you explain what are the limits of the task? What are the bigest elements in the subsets? (It is the 8 in the question text, but generally...). What is the usual cardinality of S in the solved problems? Are there any constraints that would make the task less general and possibly easier to solve?