Finding subsets that can be completed to tuples without duplicates

Question

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

This problem seems difficult, but it would be great if there was a polynomial time algorithm.

Another way to look at this is to picture the sets A_i on the left and the values on the right, with a line connecting a set and a value if the value is in the set.

Answer 1

I think the assignment algorithm might help here. The basic step would be to fix on a number in one of the Ai and then see if that number can be used with others chosen from the Aj to select a number from each set without repeat. Think of the numbers as people, and the numbers in set Aj as the people who might be used to perform task j. Then the problem of finding a different representative from each Aj is the problem of assigning a different person to each task.

Wikipedia treats the assignment problem as having all assignments possible and a cost for each http://en.wikipedia.org/wiki/Assignment_problem. In our case we can use 0 and 1 as costs to mean can do and can't do and look to see if there is a zero cost answer.

Answer 2

I'm still thinking about how to solve this, but I decided to try rewriting the question to see if it gave me any inspiration.

Given a set of N sets:

A_i = {a_i0, a_i1, ..., a_ij, ...}

find

B_i such that x is in B_i if and only if:
   x is in A_i and
   there exists {c_0, c_1, c_2, c_3, ..., c_N} such that
      c_i = x and
      c_k is in A_k for all k and
      c_k != c_l for all k != l