Databases
StackOverflow2013
Postsdbo
POFinding subsets that can be completed to tuples without duplicates
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFinding subsets that can be completed to tuples without duplicates
    text
    copied!<p>We have a collection of sets A_1,..,A_n. The goal is to find new sets for each of the old sets.</p> <pre><code>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} </code></pre> <p>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.</p> <p>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?</p> <p>Edit: here's an example. Take </p> <pre><code>A_1 = {1,2,3,4} A_2 = {2}. </code></pre> <p>Now the new sets look like this:</p> <pre><code>newA_1 = {1,3,4} newA_2 = {2} </code></pre> <p>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.</p> <p>Another example:</p> <pre><code>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} </code></pre> <p>Now the new sets are:</p> <pre><code>newA_1 = {1,2,3} newA_2 = {4,5} newA_3 = {4,5} newA_4 = {1,2,3} newA_5 = {1,2,3} </code></pre> <p>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 <code>(_,1,_,_,_)</code> or like <code>(_,_,2,_,_)</code>.</p> <p>This problem seems difficult, but it would be great if there was a polynomial time algorithm.</p> <p>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.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload