Finding subsets that can be completed to tuples without duplicates

Posted by Jules on Stack Overflow See other posts from Stack Overflow or by Jules
Published on 2010-05-06T13:41:17Z Indexed on 2010/05/06 14:08 UTC
Read the original article Hit count: 406

Filed under:
|
|

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,_,_).

© Stack Overflow or respective owner

Related posts about math

Related posts about sets