Ricerca di sottoinsiemi che possono essere completati per tuple senza duplicati

Question

Abbiamo una raccolta di set A_1, .., A_n. L'obiettivo è trovare nuovi set per ciascuno dei vecchi set.

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} 

Quindi, in parole questo dice di rimuovere tutti gli elementi da A_i che non possono essere usati per formare una tupla (a_1, .. a_n) dai set (A_1, .., a_n) tale che la tupla non contiene duplicati.

La mia domanda è come calcolare rapidamente questi nuovi set. Se implementi questa definizione generando tutte le possibili v, ciò richiederà un tempo esponenziale. Conosci un algoritmo migliore?

Modifica: ecco un esempio. Prendere

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

Ora i nuovi set di simile a questa:

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

Il 2 è stato rimosso dal A_1 perché se si sceglie la tupla sarà sempre (2,2), che non è valido perché contiene duplicati. D'altra parte 1,3,4 sono validi perché (1,2), (3,2) e (4,2) sono tuple valide.

Un altro esempio:

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} 

Ora i nuovi set sono:

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

Il 1 e 2 vengono rimossi dal set di 2 e 3 perché se si sceglie l'1 o 2 da questi set si Avrai solo 2 valori per i set 1, 4 e 5, quindi avrai sempre duplicati in tuple che assomigliano a (_,1,_,_,_) o simili a (_,_,2,_,_).

Questo problema sembra difficile, ma sarebbe bello se esistesse un algoritmo del tempo polinomiale.

Un altro modo per osservare questo è di visualizzare i set A_i a sinistra ei valori a destra, con una linea che collega un set e un valore se il valore è nell'insieme.

Answer 1

Penso che l'algoritmo di assegnazione potrebbe aiutare qui. Il passo base sarebbe quello di correggere un numero in uno dei Ai e poi vedere se quel numero può essere usato con altri scelti dall'Aj per selezionare un numero da ciascun set senza ripetere. Pensa ai numeri come persone e ai numeri nel set Aj come le persone che potrebbero essere utilizzate per eseguire l'attività j. Quindi il problema di trovare un rappresentante diverso da ciascun Aj è il problema di assegnare una persona diversa a ciascuna attività.

Wikipedia tratta il problema dell'assegnazione come se avessero tutte le assegnazioni possibili e un costo per ogni http://en.wikipedia.org/wiki/Assignment_problem. Nel nostro caso possiamo usare 0 e 1 come i costi per significare possono fare e non possono fare e cercare di vedere se c'è una risposta a costo zero.

Answer 2

Sto ancora pensando a come risolvere questo problema, ma ho deciso di provare a riscrivere la domanda per vedere se mi dava ispirazione.

Dato un insieme di N imposta:

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

trovare

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