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

Question

Quelle est la meilleure approche pour trouver si un ensemble donné (non trié) est un sous-ensemble parfait d'un ensemble principal. J'ai dû faire une validation dans mon programme où j'ai pu comparer l'ensemble de demandes de clients avec l'ensemble de capacités interne enregistré.

Je pensais faire en ayant trié les capacités internes (ne changera pas une fois enregistré) et faire une recherche binaire pour chaque élément dans l'ensemble de demandes du client. Est-ce le meilleur que je pourrais obtenir? Je soupçonnais qu'il pourrait y avoir une meilleure approche.

Une idée?

Cordialement,

Microkernel

Answer 1

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

Une bonne approche consiste à utiliser hashmaps (alias hachages alias tableaux associatifs)

Si votre surensemble n'est pas trop grand, générez un mappage hashmap chaque objet dans Le plus grand ensemble à une vraie valeur.

Ensuite, passez en 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 ensemble n'est pas un sous-ensemble de pepper. Si vous terminez la boucle sans échec, c'est.

Answer 2

dépend du nombre d'éléments dans vos ensembles. pour les grands ensembles, utilisez généralement un Hashset pour la plus grande performance de la chaîne.

Answer 3

Étant donné que vous connaissez le jeu de fonctionnalités internes, vous pouvez utiliser un perfect hash function pour tester les éléments de l'ensemble de demandes client.