Ho alcuni ricordi vaghi dei miei corsi sugli algoritmi, ma non mi viene in mente nulla di specifico.
sia S un multiset di cose a cui siamo interessati.
Come input, otteniamo T, s 1 , s 2 , ... s n , che sono tutti sottoinsiemi di S , tranne che T può avere duplicati.
Come output si ottiene se è possibile selezionare esattamente 1 elemento da ogni i in modo da finire con T. Ciò che sarebbe veramente bello è se nel caso di un errore ti sia stato detto quali s i non erano coperti da T (anche se questo non è veramente ben definito quando ci sono intersezioni non vuote nel i s).
Nel mio caso, la maggior parte delle volte non ci saranno molti elementi che appaiono in più di un i , ma devo render conto della possibilità. Inoltre, un algoritmo "online" in cui fornisci il file i in primo piano, e poi passi elementi di T uno alla volta, sarebbe conveniente.
Questo è quasi come il problema di set di colpetti esatti , ma mi viene dato T, piuttosto che cercare di trovare un sottoinsieme di T che ha questa proprietà.