Qual è l'approccio migliore per trovare se un dato insieme è un sottoinsieme perfetta di un set - Se dato sottoinsieme non è ordinato?

Question

Qual è l'approccio migliore per trovare se un dato insieme (indifferenziati) è un sottoinsieme perfetta di un set principale. Ho avuto modo di fare un po 'di validazione nel mio programma in cui ho avuto modo di confrontare i clienti richiesta impostate con il set registrato capacità interna.

ho pensato di fare avendo insieme capacità interna allineati (non cambierà una volta registrato) e fare ricerca binaria per ogni elemento nel set richiesta del cliente. È il meglio che ho potuto ottenere? Sospettavo che ci potrebbe essere l'approccio migliore.

Qualche idea?

Saluti,

Microkernel

Answer 1

Supponendo che la lingua scelta non implementa una classe set con "contiene in un set" Metodo già come Java fa con HashSet ...

Un approccio è quello di usare buon HashMaps (aka hash aka associativa array)

Se il superset non è troppo grande, generare un HashMap mappare ogni oggetto nel set più grande per un valore vero.

Poi, un ciclo su ogni elemento in un sottogruppo. Prova a trovare l'elemento nella HashMap generato. se non si riesce, il tuo piccolo insieme non è un sottoinsieme peoper. Se hai finito il ciclo senza venir meno, lo è.

Answer 2

dipende da quanti elementi sono in vostri set. per i set più grandi, di solito utilizzare una hashset per i giri mainset fuori le migliori prestazioni.

Answer 3

Dal momento che si conosce la capacità interna impostata è possibile utilizzare un perfetta funzione di hash per testare la elementi del set richiesta del cliente.