Share
L'ensemble est un type de collection qui implémente les algorithmes d'ensembles algébriques de base, notamment l'union, l'intersection, la différence et la différence symétrique. Chacun de ces algorithmes sera expliqué en détail dans leurs sections respectives.
Conceptuellement, les ensembles sont des collections d'objets qui ont souvent des points communs. Par exemple, nous pourrions avoir un ensemble contenant des entiers pairs positifs:
[2, 4, 6, 8, 10,…]
Et un ensemble contenant des entiers positifs impairs:
[1, 3, 5, 7, 9,…]
Ces deux ensembles n'ont aucune valeur en commun. Considérons maintenant un troisième ensemble comprenant tous les facteurs du nombre 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Étant donné ces ensembles, nous pouvons maintenant répondre à la question «Quels facteurs de 100 sont impairs?» En examinant l’ensemble des entiers impairs et l’ensemble des facteurs de 100 et en recherchant les valeurs présentes dans les deux ensembles. Mais nous pourrions aussi répondre à des questions telles que «Quels nombres impairs ne sont pas des facteurs de 100?» Ou «Quels nombres positifs, pairs ou impairs, ne sont pas des facteurs de 100?
Cela peut ne pas sembler très utile, mais c'est parce que l'exemple est quelque peu artificiel. Imaginez si les postes étaient tous les employés d’une entreprise et tous les employés qui avaient suivi la formation annuelle obligatoire.
Nous pourrions facilement répondre à la question «Quels employés n’ont pas suivi la formation obligatoire?
Nous pouvons continuer à ajouter des ensembles supplémentaires et à commencer à répondre à des questions très complexes telles que: «Quels employés à temps plein de l'équipe des ventes à qui une carte de crédit d'entreprise a été émise n'ont pas suivi la formation obligatoire sur le nouveau processus de compte rendu des dépenses?
le Ensemble la classe implémente le IEnumerable interface et accepte un argument générique qui devrait être un IComparable type (le test d'égalité est nécessaire pour que les algorithmes définis fonctionnent).
Les membres de l'ensemble seront contenus dans un .NET liste classe, mais en pratique, les ensembles sont souvent contenus dans des arborescences telles qu’un arbre de recherche binaire. Ce choix de conteneur sous-jacent affecte la complexité des différents algorithmes. Par exemple, en utilisant le liste, Contient a une complexité de O (n), alors que l’utilisation d’un arbre donnerait O (log n) en moyenne.
En plus des méthodes que nous allons mettre en place, le Ensemble inclut un constructeur par défaut et un qui accepte un IEnumerable d'éléments pour remplir l'ensemble avec.
Classe publique Set: IEnumerable où T: IComparable privé en lecture seule List _items = new List (); public Set () public Set (IEnumerable items) AddRange (items); public void Add (élément T); public void AddRange (éléments IEnumerable); public bool Remove (élément T); public bool Contains (élément T); public int Count get; public Set Union (Set other); public Set Intersection (Set other); public Set Difference (Set other); public Set SymmetricDifference (Set other); IEnumerator public GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Comportement | Ajoute l'élément à l'ensemble. Si l'élément existe déjà dans l'ensemble, une exception InvalidOperationException est levée.. |
| Performance | Sur) |
Lors de la mise en œuvre du Ajouter algorithme, une décision doit être prise: l'ensemble autorisera-t-il les éléments en double ou pas? Par exemple, étant donné l'ensemble suivant:
[1, 2, 3, 4]
Si l'appelant tente d'ajouter la valeur trois, l'ensemble devient:
[1, 2, 3, 3, 4]
Bien que cela puisse être acceptable dans certains contextes, ce n'est pas le comportement que nous allons mettre en œuvre. Imaginez un ensemble contenant tous les étudiants d'un collège local. Il ne serait pas logique de permettre à un même élève d'être ajouté deux fois à l'ensemble. En fait, tenter de le faire est probablement une erreur (et sera traité comme tel dans cette implémentation).
Remarque: Ajouter utilise le Contient Méthode
Accentsconagua
public void Ajouter (élément T) if (contient (élément)) lancer une nouvelle exception InvalidOperationException ("L'élément existe déjà dans l'ensemble"); _items.Add (item); | Comportement | Ajoute plusieurs éléments à l'ensemble. Si un membre de l'énumérateur d'entrée existe dans l'ensemble ou s'il existe des éléments en double dans l'énumérateur d'entrée, une exception InvalidOperationException sera levée.. |
| Performance | O (mn), où m est le nombre d'éléments dans l'énumération en entrée et n le nombre d'éléments actuellement dans l'ensemble. |
public void AddRange (IEnumerable items) foreach (élément T dans éléments) Ajouter (élément);
| Comportement | Supprime la valeur spécifiée de l'ensemble si trouvé et renvoie true. Si l'ensemble ne contient pas la valeur spécifiée, false est renvoyé.. |
| Performance | Sur) |
public bool Remove (élément T) return _items.Remove (élément);
| Comportement | Renvoie true si le jeu contient la valeur spécifiée. Sinon, il retourne faux. |
| Performance | Sur) |
public bool Contains (élément T) return _items.Contains (élément);
| Comportement | Retourne le nombre d'éléments dans le jeu ou 0 si le jeu est vide. |
| Performance | O (1) |
public int Count get return _items.Count;
| Comportement | Renvoie un énumérateur pour tous les éléments de l'ensemble.. |
| Performance | O (1) pour renvoyer l'énumérateur. L'énumération de tous les éléments a une complexité de O (n). |
IEnumerator public GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Comportement | Retourne un nouvel ensemble qui est le résultat de l'union des ensembles actuel et d'entrée.. |
| Performance | O (mn), où m et n sont le nombre d'éléments dans les ensembles fourni et actuel, respectivement. |
L'union de deux ensembles est un ensemble contenant tous les éléments distincts qui existent dans les deux ensembles..
Par exemple, deux ensembles (chacun représenté en rouge):
Deux jeux d'entrées avant l'opération d'union Lorsque l'opération d'union est effectuée, le jeu de sortie contient tous les éléments des deux jeux. S'il existe des éléments dans les deux ensembles, une seule copie de chaque élément est ajoutée à l'ensemble de sortie..
Le jeu de sortie après l'opération d'union (les éléments retournés sont en jaune) Un exemple plus concret peut être vu lorsque nous unissons plusieurs ensembles d’entiers:
[1, 2, 3, 4] syndicat [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (Set autre) Set result = new Set (_items); foreach (T item dans other._items) if (! Contains (item)) result.Add (item); return result;
| Comportement | Renvoie un nouvel ensemble résultant de l'opération d'intersection des ensembles actuel et d'entrée.. |
| Performance | O (mn), où m et n sont le nombre d'éléments dans les ensembles fourni et actuel, respectivement. |
Intersection est le point où deux ensembles "se croisent", par exemple, leurs membres communs. En utilisant le diagramme de Venn de l'exemple d'union, l'intersection des deux ensembles est montrée ici:
L'intersection des deux jeux d'entrées est indiquée en jaune Ou, en utilisant des ensembles d'entiers:
[1, 2, 3, 4] couper [3, 4, 5, 6] = [3, 4]
public Set Intersection (Set other) Set result = new Set (); foreach (T item dans _items) if (other._items.Contains (item)) result.Add (item); return result;
| Comportement | Retourne un nouvel ensemble qui est le résultat de l'opération de différence entre les ensembles actuel et d'entrée.. |
| Performance | O (mn), où m et n sont le nombre d'éléments dans les ensembles fourni et actuel, respectivement. |
La différence, ou différence d’ensemble, entre deux ensembles correspond aux éléments présents dans le premier ensemble (l’ensemble dont Différence méthode est appelée), mais n’existe pas dans le deuxième ensemble (paramètre de la méthode). Le diagramme de Venn pour cette méthode est montré ici avec le jeu retourné en jaune:
La différence de set entre deux sets Ou, en utilisant des ensembles d'entiers:
[1, 2, 3, 4] différence [3, 4, 5, 6] = [1, 2]
public Set Difference (Set other) Set result = new Set (_items); foreach (T item dans other._items) result.Remove (item); retourne le résultat;
| Comportement | Renvoie un nouvel ensemble résultant de l'opération de différence symétrique des ensembles actuel et d'entrée.. |
| Performance | O (mn), où m et n sont le nombre d'éléments dans les ensembles fourni et actuel, respectivement. |
La différence symétrique de deux ensembles est un ensemble dont les membres sont les éléments qui n'existent que dans l'un ou l'autre des ensembles. Le diagramme de Venn de cette méthode est montré ici avec le jeu retourné en jaune
La différence symétrique de deux ensembles Ou, en utilisant des ensembles entiers:
[1, 2, 3, 4] différence symétrique [3, 4, 5, 6] = [1, 2, 5, 6]
Vous avez peut-être remarqué qu'il s'agit de l'opposé exact de l'opération d'intersection. Dans cet esprit, voyons ce qu'il faudrait faire pour trouver la différence symétrique en utilisant uniquement les algorithmes d'ensemble que nous avons déjà examinés..
Marchons à travers ce que nous voulons.
Nous voulons un ensemble contenant tous les éléments des deux ensembles, à l'exception de ceux qui existent dans les deux. Ou dit d'une autre manière, nous voulons l'union des deux ensembles sauf pour l'intersection des deux ensembles. Nous voulons la différence entre l'union et l'intersection des deux ensembles.
Pas à pas, ça ressemble à ça:
[1, 2, 3, 4] syndicat [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] intersection [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] faire la différence [3, 4] = [1, 2, 5, 6]
Ce qui donne le résultat obtenu: ([1, 2, 5, 6]).
public Set SymmetricDifference (Set other) Set union = Union (other); Définir l'intersection = Intersection (autre); retour union.Difference (intersection);
Vous vous demandez peut-être pourquoi je n'ai pas ajouté de IsSubset méthode. Ce type de méthode est couramment utilisé pour déterminer si un ensemble est entièrement contenu dans un autre ensemble. Par exemple, nous pourrions vouloir savoir si:
[1, 2, 3] est un sous-ensemble [0, 1, 2, 3, 4, 5] = vrai
Tandis que:
[1, 2, 3] est un sous-ensemble [0, 1, 2] = faux
La raison pour laquelle je n'ai pas détaillé un IsSubset méthode est qu'il peut être effectué en utilisant des moyens existants. Par exemple:
[1, 2, 3] différence [0, 1, 2, 3, 4, 5] = []
Un ensemble de résultats vide indique que l'ensemble du premier ensemble était contenu dans le second, nous savons donc que le premier est un sous-ensemble complet du second. Un autre exemple, utilisant l'intersection:
[1, 2, 3] intersection [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Si le jeu de sorties a le même nombre d'éléments que le jeu d'entrées, nous savons que le jeu d'entrées est un sous-ensemble du second jeu.
Dans une classe Set à usage général, avoir un IsSubset méthode pourrait être utile (et pourrait être mis en œuvre de manière plus optimale); Cependant, je voulais faire remarquer qu'il ne s'agissait pas nécessairement d'un nouveau comportement, mais plutôt d'une autre façon de penser aux opérations existantes..
