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.