Sprawdzenie, czy zbiór elementów A zawiera zbiór elementów B

pytanie zadane 18 listopada 2017 w Algorytmy przez Schizohatter Nałogowiec (39,600 p.)
edycja 18 listopada 2017 przez Schizohatter

Hej. Tym razem to ja zadam pytanie, bo może ktoś będzie miał jakiś pomysł, jak rozwiązać ten problem stosunkowo wydajnie.

Posiadam X zbiorów elementów. Te zbiory są w przybliżeniu losowe, np. jeden zbiór to: [A, A, A, B, B, C, C, C, C]. Oprócz tablicy, zbiór może być zapisany także jako: { A: 3, B: 2, C: 4 }

Posiadam także Y-liczbę recept. Recepta zawiera informację o elementach (pochodzących ze zbiorów) potrzebnych do jej stworzenia. Np Recepta P: [A, A, B, C, C] może być stworzona z ww. zbioru. Nie jest konieczne wykorzystanie wszystkich elementów ze zbioru (mogą pozostać jakieś resztki) Sposób zapisu pojedynczych recept, jak i całego zbioru recept nie jest ustalony.

Teraz muszę porównać każdy z X zbiorów z tabelą recept. Tutaj wkraczacie Wy z Waszymi świetnymi pomysłami :) Jak to zrobić dobrze? Język: JavaScript.

Najprostszym (najbardziej brute-force) rozwiązaniem, będzie oczywiście sprawdzenie każdej recepty po kolei, czy wszystkie jej składniki znajdują się w zbiorze. Ale to rozwiązanie brute-force i przy wielu zbiorach doprowadzi do zawalenia wydajności. A cały ten algorytm będzie odpalany kilka razy w ciągu sekundy, pracując na: 300 zbiorach, po ok. 8 elementów, przy kilku receptach.

Być może wykorzystanie zapisu zbioru jako obiektu i recepty jako obiektu, a następnie porównanie wszystkich kluczy-wartości recepty z kluczami-wartościami obiektu? Może to załatwi sprawę? A może można to jakoś inaczej, sprytniej zrobić?

komentarz 18 listopada 2017 przez niezalogowany

Czy zestaw zbiorów jest stały?
Czy mogę założyć, że poszczególne składniki to stringi i spróbować zaimplementować to w JS?

komentarz 18 listopada 2017 przez Schizohatter Nałogowiec (39,600 p.)

Możesz założyć, że poszczególne składniki to stringi.

Liczba zbiorów jest stała w każdej iteracji algorytmu. Jednak zmienia się ich skład. Ogólnie to zbiory przerzucają między sobą elementy w sposób losowy, a następnie wykonywane jest sprawdzanie elementów z receptami.