Finding subsets that can be completed to tuples without duplicates
- by Jules
We have a collection of sets A_1,..,A_n. The goal is to find new sets for each of the old sets.
newA_i = {a_i in A_i such that there exist (a_1,..,a_n) in (A1,..,An) with no a_k = a_j for all k and j}
So in words this says that we remove all the elements from A_i that can't be used to form a tuple (a_1,..a_n) from the sets (A_1,..,A_n) such that the tuple doesn't contain duplicates.
My question is how to compute these new sets quickly. If you just implement this definition by generating all possible v's this will take exponential time. Do you know a better algorithm?
Edit: here's an example. Take
A_1 = {1,2,3,4}
A_2 = {2}.
Now the new sets look like this:
newA_1 = {1,3,4}
newA_2 = {2}
The 2 has been removed from A_1 because if you choose it the tuple will always be (2,2) which is invalid because it contains duplicates. On the other hand 1,3,4 are valid because (1,2), (3,2) and (4,2) are valid tuples.
Another example:
A_1 = {1,2,3}
A_2 = {1,4,5}
A_3 = {2,4,5}
A_4 = {1,2,3}
A_5 = {1,2,3}
Now the new sets are:
newA_1 = {1,2,3}
newA_2 = {4,5}
newA_3 = {4,5}
newA_4 = {1,2,3}
newA_5 = {1,2,3}
The 1 and 2 are removed from sets 2 and 3 because if you choose the 1 or 2 from these sets you'll only have 2 values left for sets 1, 4 and 5, so you will always have duplicates in tuples that look like (_,1,_,_,_) or like (_,_,2,_,_).
