Encontrar subconjuntos que se pueden completar en tuplas sin duplicados

Question

Tenemos una colección de conjuntos A_1, .., A_n. El objetivo es encontrar nuevos conjuntos para cada uno de los conjuntos antiguos.

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} 

Así, en palabras este dice que eliminamos todos los elementos de A_i que no pueden ser utilizados para formar una tupla (a_1, .. a_n) de los conjuntos (A_1, .., A_n) tal que la tupla no contiene duplicados.

Mi pregunta es cómo calcular estos nuevos conjuntos rápidamente. Si acaba de implementar esta definición generando todas las posibles v, esto tomará tiempo exponencial. ¿Conoces un mejor algoritmo?

Editar: aquí hay un ejemplo. Tome

A_1 = {1,2,3,4} 
A_2 = {2}. 

Ahora los nuevos conjuntos de aspecto:

newA_1 = {1,3,4} 
newA_2 = {2} 

La 2 ha sido eliminado de A_1 porque si decide que la tupla siempre será (2,2), que no es válido porque contiene duplicados. Por otro lado, 1,3,4 son válidos porque (1,2), (3,2) y (4,2) son tuplas válidas.

Otro ejemplo:

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} 

Ahora los nuevos conjuntos son:

newA_1 = {1,2,3} 
newA_2 = {4,5} 
newA_3 = {4,5} 
newA_4 = {1,2,3} 
newA_5 = {1,2,3} 

El 1 y 2 son retirados de los conjuntos 2 y 3, ya que si se elige la 1 o 2 de estos conjuntos se Solo le quedan 2 valores para los conjuntos 1, 4 y 5, por lo que siempre tendrá duplicados en tuplas que se parecen al (_,1,_,_,_) o como (_,_,2,_,_).

Este problema parece difícil, pero sería genial si hubiera un algoritmo de tiempo polinomial.

Otra forma de ver esto es visualizar los conjuntos A_i a la izquierda y los valores a la derecha, con una línea que conecta un conjunto y un valor si el valor está en el conjunto.

Answer 1

Creo que el algoritmo de asignación podría ayudar aquí. El paso básico sería fijar un número en uno de los Ai y luego ver si ese número se puede usar con otros elegidos de Aj para seleccionar un número de cada conjunto sin repetir. Piense en los números como personas, y los números en el conjunto Aj como las personas que podrían usarse para realizar la tarea j. Entonces, el problema de encontrar un representante diferente de cada Aj es el problema de asignar una persona diferente a cada tarea.

Wikipedia trata el problema de asignación teniendo todas las asignaciones posibles y un costo por cada http://en.wikipedia.org/wiki/Assignment_problem. En nuestro caso, podemos usar 0 y 1 como costos que mean puede y no puede hacer y ver si hay una respuesta de costo cero.

Answer 2

Todavía estoy pensando en cómo resolver esto, pero decidí intentar reescribir la pregunta para ver si me inspiraba.

Dado un conjunto de n conjuntos:

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

encuentran

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