Share
De set is een verzamelingstype dat de basisalgoritmen van de algebraïsche set implementeert, inclusief unie, intersectie, verschil en symmetrisch verschil. Elk van deze algoritmen zal in detail worden beschreven in hun respectieve secties.
Conceptueel zijn sets verzamelingen objecten die vaak wat gemeenschappelijkheid hebben. We hebben bijvoorbeeld een set met positieve even gehele getallen:
[2, 4, 6, 8, 10, ...]
En een set met positieve oneven gehele getallen:
[1, 3, 5, 7, 9, ...]
Deze twee sets hebben geen gemeenschappelijke waarden. Overweeg nu een derde reeks die alle factoren van nummer 100 is:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Met deze sets kunnen we nu de vraag 'Welke factoren van 100 zijn vreemd?' Beantwoorden door naar de set van oneven gehele getallen en de set factoren van 100 te kijken en te zien welke waarden in beide sets bestaan. Maar we kunnen ook vragen beantwoorden zoals: "Welke oneven getallen zijn geen 100-factoren?" Of "Welke positieve getallen, even of oneven, zijn geen factoren van 100?"
Dit lijkt misschien niet erg nuttig, maar dat komt omdat het voorbeeld enigszins is gekunsteld. Stel je voor dat de sets elke werknemer in een bedrijf waren en elke werknemer die de verplichte jaarlijkse training had voltooid.
We zouden gemakkelijk de vraag kunnen beantwoorden: "Welke werknemers hebben de verplichte training niet voltooid?"
We kunnen doorgaan met het toevoegen van aanvullende sets en beginnen met het beantwoorden van zeer complexe vragen, zoals: "Welke fulltime medewerkers van het verkoopteam die een bedrijfskredietkaart hebben gekregen, hebben de verplichte training over het nieuwe onkostenrapporteringsproces niet bijgewoond?"
De set klasse implementeert de IEnumerable interface en accepteert een generiek argument dat een IComparable type (testen op gelijkheid is nodig om de ingestelde algoritmen te laten functioneren).
De leden van de set worden opgenomen in een .NET Lijst klasse, maar in de praktijk zijn sets vaak opgenomen in boomstructuren, zoals een binaire zoekboom. Deze keuze van de onderliggende container beïnvloedt de complexiteit van de verschillende algoritmen. Gebruik bijvoorbeeld de Lijst, bevat heeft een complexiteit van O (n), terwijl het gebruik van een boom gemiddeld resulteert in O (log n).
Naast de methoden die we zullen implementeren, de set bevat een standaardconstructor en een die een accepteert IEnumerable van items om de set mee te vullen.
public class Set: IEnumerable where T: ICcomparable private readonly List _items = new List (); public Set () public Set (IEnumerable items) AddRange (items); public void Toevoegen (T item); openbare ongeldige AddRange (IEnumerable items); public bool verwijderen (T item); public bool Bevat (T item); openbare int graaf krijg; openbare Set Union (andere instellen); public Set Intersection (andere reeks instellen); Openbaar verschil instellen (andere instellen); public Set SymmetricDifference (Set other); openbare IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Gedrag | Voegt het item toe aan de set. Als het item al in de set bestaat, wordt een ongeldige bewerkingsexceptie gegenereerd. |
| Prestatie | Op) |
Bij de implementatie van de Toevoegen algoritme, moet een beslissing worden genomen: zal de set dubbele items toestaan of niet? Bijvoorbeeld, gezien de volgende set:
[1, 2, 3, 4]
Als de beller probeert de waarde drie toe te voegen, wordt de set:
[1, 2, 3, 3, 4]
Hoewel dit in sommige contexten acceptabel kan zijn, is het niet het gedrag dat we gaan implementeren. Stel je een set voor die alle studenten op een lokaal college bevat. Het zou niet logisch zijn om dezelfde student twee keer toe te voegen aan de set. In feite is een poging hiertoe waarschijnlijk een fout (en zal als zodanig worden behandeld in deze implementatie).
Notitie: Add gebruikt de bevat Methode
Accentsconagua
public void Toevoegen (T item) if (Bevat (item)) gooi nieuwe InvalidOperationException ("Item bestaat al in Set"); _items.Add (item); | Gedrag | Voegt meerdere items toe aan de set. Als een lid van de invoer-teller in de set voorkomt, of als er dubbele items in de invoervaarder zijn, wordt een ongeldige bewerkingsexceptie gegenereerd. |
| Prestatie | O (mn), waarbij m het aantal items in de invoer-opsomming is en n het aantal items is dat momenteel in de set is. |
public void AddRange (IEnumerable items) foreach (T item in items) Toevoegen (item);
| Gedrag | Verwijdert de opgegeven waarde uit de set als deze wordt gevonden, waarbij true wordt geretourneerd. Als de set de opgegeven waarde niet bevat, wordt false geretourneerd. |
| Prestatie | Op) |
public bool Remove (T item) return _items.Remove (item);
| Gedrag | Retourneert true als de set de opgegeven waarde bevat. Anders wordt false geretourneerd. |
| Prestatie | Op) |
public bool Bevat (T item) return _items.Contains (item);
| Gedrag | Retourneert het aantal items in de set of 0 als de set leeg is. |
| Prestatie | O (1) |
public int Count krijg return _items.Count;
| Gedrag | Retourneert een enumerator voor alle items in de set. |
| Prestatie | O (1) om de teller te retourneren. Het opsommen van alle items heeft een complexiteit van O (n). |
openbare IEnumerator GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Gedrag | Retourneert een nieuwe set die het resultaat is van de uniebewerking van de stroom en de ingevoerde reeks. |
| Prestatie | O (mn), waarbij m en n respectievelijk het aantal items in de opgegeven en huidige sets zijn. |
De combinatie van twee sets is een set die alle afzonderlijke items bevat die in beide sets voorkomen.
Bijvoorbeeld, gegeven twee sets (elk weergegeven in rood):
Twee invoersets voor de union-bewerking Wanneer de union-bewerking wordt uitgevoerd, bevat de uitvoerreeks alle items in beide sets. Als er items in beide sets aanwezig zijn, wordt slechts één kopie van elk item toegevoegd aan de uitvoerset.
De uitvoer wordt ingesteld na de verbindingsbewerking (geretourneerde artikelen zijn geel) Een concreter voorbeeld is te zien wanneer we meerdere sets van gehele getallen samenvoegen:
[1, 2, 3, 4] unie [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (andere instellen) Set result = nieuwe set (_items); foreach (T item in other._items) if (! Bevat (item)) result.Add (item); retourresultaat;
| Gedrag | Retourneert een nieuwe set die het resultaat is van de intersectiebewerking van de huidige en ingevoerde sets. |
| Prestatie | O (mn), waarbij m en n respectievelijk het aantal items in de opgegeven en huidige sets zijn. |
Kruising is het punt waarop twee sets elkaar snijden, bijvoorbeeld hun gemeenschappelijke leden. Met behulp van het Venn-diagram uit het vakbondsvoorbeeld wordt hier de kruising van de twee sets getoond:
Het snijpunt van de twee invoersets wordt geel weergegeven Of, met behulp van sets van gehele getallen:
[1, 2, 3, 4] snijden [3, 4, 5, 6] = [3, 4]
public Set Intersection (andere instellen) Set result = nieuwe set (); foreach (T item in _items) if (other._items.Contains (item)) result.Add (item); retourresultaat;
| Gedrag | Retourneert een nieuwe set die het resultaat is van de verschilbewerking van de huidige en ingevoerde sets. |
| Prestatie | O (mn), waarbij m en n respectievelijk het aantal items in de opgegeven en huidige sets zijn. |
Het verschil, of het set-verschil, tussen twee sets bestaat uit de items die in de eerste set bestaan (de set waarvan Verschil methode wordt aangeroepen), maar bestaan niet in de tweede set (de parameter van de methode). Het Venn-diagram voor deze methode wordt hier weergegeven met de geretourneerde set in geel:
Het set verschil tussen twee sets Of, met behulp van sets van gehele getallen:
[1, 2, 3, 4] verschil [3, 4, 5, 6] = [1, 2]
public Set Difference (Set other) Set result = new Set (_items); foreach (T item in other._items) result.Remove (item); retour resultaat;
| Gedrag | Retourneert een nieuwe set die het resultaat is van de symmetrische verschilbewerking van de stroom- en invoersets. |
| Prestatie | O (mn), waarbij m en n respectievelijk het aantal items in de opgegeven en huidige sets zijn. |
Het symmetrische verschil van twee sets is een set waarvan de leden die items zijn die alleen in de ene of de andere set voorkomen. Het Venn-diagram voor deze methode wordt hier weergegeven met de geretourneerde set in geel
Het symmetrische verschil van twee sets Of, met behulp van integer sets:
[1, 2, 3, 4] symmetrisch verschil [3, 4, 5, 6] = [1, 2, 5, 6]
U hebt misschien gemerkt dat dit precies het tegenovergestelde is van de kruisingsoperatie. Laten we met dit in gedachten eens kijken wat het zou kosten om het symmetrische verschil te vinden met alleen de ingestelde algoritmen waar we al naar keken.
Laten we doorlopen wat we willen.
We willen een set met alle items van beide sets, behalve die van beide. Of anders gezegd, we willen de unie van beide sets, behalve de kruising van beide sets. We willen het vaste verschil tussen de unie en de kruising van beide sets.
Stap voor stap ziet het er zo uit:
[1, 2, 3, 4] unie [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] kruispunt [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] verschil instellen [3, 4] = [1, 2, 5, 6]
Dat levert de resulterende set op die we wilden: ([1, 2, 5, 6]).
public Set SymmetricDifference (Set other) Set union = Union (other); Snijpunt instellen = snijpunt (ander); return union.Verschil (kruispunt);
Je vraagt je misschien af waarom ik er geen heb toegevoegd IsSubset methode. Dit type methode wordt meestal gebruikt om te bepalen of een set volledig in een andere set is opgenomen. We willen bijvoorbeeld weten of:
[1, 2, 3] is subset [0, 1, 2, 3, 4, 5] = waar
Terwijl:
[1, 2, 3] is subset [0, 1, 2] = vals
De reden waarom ik niet heb gedetailleerd IsSubset methode is dat het kan worden uitgevoerd met behulp van bestaande middelen. Bijvoorbeeld:
[1, 2, 3] verschil [0, 1, 2, 3, 4, 5] = []
Een lege resultatenset geeft aan dat de volledige eerste set zich in de tweede set bevond, dus we weten dat de eerste set een volledige subset van de tweede is. Nog een voorbeeld, met behulp van kruising:
[1, 2, 3] kruispunt [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Als de uitvoerreeks hetzelfde aantal elementen heeft als de ingevoerde reeks, weten we dat de invoerset een subset van de tweede reeks is.
In een algemene reeksklasse, met een IsSubset methode kan nuttig zijn (en zou beter kunnen worden geïmplementeerd); Ik wilde echter duidelijk maken dat dit niet noodzakelijk een nieuw gedrag is, maar gewoon een andere manier van denken over bestaande operaties.
