Esiste una soluzione generale a questo problema di mappatura?

0

Ho riscontrato questo interessante problema al lavoro e sembra il tipo di problema che potrebbe avere una soluzione ben nota, mi scuso in anticipo se una parte della mia terminologia è errata o confusa.

Ho un set di input e un set di output, ogni input si connette a ogni output tranne quando specificato in un dizionario che associa un output a un elenco di input a cui non può essere collegato. Poiché è previsto che la maggior parte degli ingressi si connetterà alla maggior parte delle uscite, salva la memoria per memorizzarla solo quando un ingresso non può connettersi a un particolare output.

Voglio creare un insieme di coppie di elenchi di quantità minima come:

pair<list<Output>, list<Input>> 

dove tutte le uscite possono essere collegate agli ingressi.

così come un esempio gli input sono [a, b, c, d] e le uscite sono [A, B, C, D] dove abbiamo una mappa di uscite che non possono essere collegate a certi input:

A -> [a, b]
B -> []
C -> []
D -> [c, d]

quindi in questo caso avremmo coppie:

([c, d], [A, B, C])
([a, b, c, d], [B]) 
([a, b, c, d], [C]) 
([a, b], [B, C, D])

Che può essere ridotto al minimo set "spanning":

([c, d], [A, B, C])    
([a, b, c, d], [B, C]) 
([a, b], [B, C, D])

Per considerazioni pratiche ci si aspetta che di solito siano dell'ordine di circa 10 uscite e di diverse migliaia di input.

    
posta user3678912 03.08.2017 - 15:38
fonte

0 risposte

Leggi altre domande sui tag