Quelle est la meilleure approche pour trouver si un ensemble donné est un sous-ensemble parfait d'un ensemble - Si sous-ensemble donné ne sont pas triées?

Question

Quelle est la meilleure approche pour trouver si un ensemble (non triés) est un sous-ensemble parfait d'un ensemble principal. Je dois faire une validation dans mon programme où je suis arrivé à comparer les clients demander un jeu avec le jeu de capacité interne enregistrée.

Je pensais que de faire en ayant une capacité interne de jeu triée (ne changera pas une fois enregistré) et faire la recherche binaire pour chaque élément dans l'ensemble de la demande du client. Est-ce le meilleur que je pourrais obtenir? Je me doutais bien qu'il pourrait y avoir une meilleure approche.

Toute idée?

Cordialement,

Microkernel

Answer 1

En supposant que la langue de votre choix ne met pas en œuvre une classe de set avec « contient dans un ensemble » méthode déjà comme Java avec HashSet ...

Une bonne approche consiste à utiliser hashmaps (aka hash aka tableaux associatifs)

Si votre surensemble est pas trop grand, générer un hashmap mappage de chaque objet dans l'ensemble plus large à une valeur réelle.

Ensuite, une boucle sur chaque élément d'un sous-ensemble. Essayez de trouver l'élément dans le hashmap généré. si vous échouez, votre petit jeu n'est pas un sous-ensemble de peoper. Si vous avez terminé la boucle sans défaut, il est.

Answer 2

il dépend de nombreux éléments sont dans vos jeux. pour de plus grands ensembles, utilisez généralement un HashSet pour les tours de mainset sur les meilleures performances.

Answer 3

Puisque vous connaissez la capacité interne défini, vous pouvez utiliser un fonction de hachage parfaite pour tester la éléments de l'ensemble de la demande du client.