Share
Setet er en samlingstype som implementerer de grunnleggende algebraiske settalgoritmene, inkludert fagforening, skjæringspunkt, forskjell og symmetrisk forskjell. Hver av disse algoritmene vil bli forklart i detalj i sine respektive seksjoner.
Konseptuelt sett er samlinger av gjenstander som ofte har noe felles. For eksempel kan vi ha et sett som inneholder positive like heltall:
[2, 4, 6, 8, 10, ...]
Og et sett som inneholder positive odde heltall:
[1, 3, 5, 7, 9, ...]
Disse to settene har ingen fellesverdier. Nå vurderer et tredje sett som er alle faktorene i nummeret 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Gitt disse settene, kan vi nå svare på spørsmålet "Hvilke faktorer på 100 er merkelige?" Ved å se på sett med odde heltall og settet av faktorer på 100 og se hvilke verdier som eksisterer i begge settene. Men vi kunne også svare på spørsmål som "Hvilke merkelige tall er ikke 100-faktorene?" Eller "Hvilke positive tall, like eller ulige, er ikke faktorer på 100?"
Dette kan ikke virke veldig nyttig, men det er fordi eksemplet er noe opptatt. Tenk deg om settene var hver ansatt hos et selskap og hver ansatt som hadde fullført den obligatoriske årlige opplæringen.
Vi kunne enkelt svare på spørsmålet "Hvilke ansatte har ikke fullført obligatorisk trening?"
Vi kan fortsette å legge til flere sett og begynne å svare på svært komplekse spørsmål som, "Hvilke heltidsansatte på salgsteamet som har blitt utstedt et bedriftskredittkort, har ikke deltatt i obligatorisk trening på den nye regnskapsrapporteringsprosessen?"
De Sett klassen implementerer IEnumerable grensesnitt og aksepterer et generisk argument som burde være en IComparable type (testing for likestilling er nødvendig for at de valgte algoritmer skal fungere).
Medlemmene av settet vil være inneholdt i et .NET Liste klassen, men i praksis settes ofte sett i trestrukturer som et binært søketre. Dette valget av underliggende container påvirker kompleksiteten til de forskjellige algoritmer. For eksempel bruker du Liste, inneholder har en kompleksitet av O (n), mens bruk av et tre vil resultere i O (log n) i gjennomsnitt.
I tillegg til metodene vi skal implementere, Sett inkluderer en standardkonstruktor og en som aksepterer en IEnumerable av elementer for å fylle settet med.
offentlig klasse Set: IEnumerable hvor T: Ukjent privat readonly Liste _items = ny liste (); offentlige sett () offentlige sett (IEnumerable elementer) AddRange (elementer); offentlig tomrom Legg til (T-element); offentlig tomrom AddRange (IEnumerable elementer); offentlig bool Fjern (T element); offentlig bool Inneholder (T-element); offentlig inntekt get; Offentlig Sett Union (Angi andre); Offentlig Sett Intersection (sett andre); offentlig sett forskjell (sett andre); offentlig sett symmetrisk forskjell (sett andre); offentlig IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Oppførsel | Legger til elementet i settet. Hvis elementet allerede finnes i settet, kastes en InvalidOperationException. |
| Opptreden | På) |
Når du implementerer Legg til algoritme, må en beslutning gjøres: vil settet tillate dupliserte elementer eller ikke? For eksempel, gitt følgende sett:
[1, 2, 3, 4]
Hvis den som ringer forsøker å legge til verdien tre, blir settet:
[1, 2, 3, 3, 4]
Selv om dette kan være akseptabelt i noen sammenhenger, er det ikke oppførselen vi skal gjennomføre. Tenk deg et sett som inneholder alle studentene på en lokal høyskole. Det ville ikke være logisk å la samme student bli lagt til settet to ganger. Faktisk er det sannsynligvis en feil å forsøke å gjøre (og vil bli behandlet som sådan i denne implementeringen).
Merk: Legg til bruker inneholder Metode
Accentsconagua
offentlig tomrom Legg til (T-punkt) hvis (Inneholder (element)) kast nytt InvalidOperationException ("Artikkel eksisterer allerede i Set"); _items.Add (item); | Oppførsel | Legger til flere elementer i settet. Hvis noen medlem av inngangsregulatoren finnes i settet, eller hvis det er dupliserte elementer i inntastingsregulatoren, vil en InvalidOperationException bli kastet. |
| Opptreden | O (mn), hvor m er antall elementer i inngangsregistreringen og n er antall elementer som for tiden er i settet. |
public void AddRange (IEnumerable items) foreach (T element i elementer) Legg til (element);
| Oppførsel | Fjerner den angitte verdien fra settet hvis det er funnet, og returnerer sant. Hvis settet ikke inneholder den angitte verdien, returneres falsk. |
| Opptreden | På) |
offentlig bool Fjern (T element) return _items.Remove (item);
| Oppførsel | Returnerer sant hvis settet inneholder den angitte verdien. Ellers returnerer den falsk. |
| Opptreden | På) |
offentlig bool Inneholder (T element) return _items.Contains (item);
| Oppførsel | Returnerer antall elementer i settet eller 0 hvis settet er tomt. |
| Opptreden | O (1) |
offentlig int Count get return _items.Count;
| Oppførsel | Returnerer en oppregner for alle elementene i settet. |
| Opptreden | O (1) for å returnere taleren. Oppsummering av alle elementene har en kompleksitet av O (n). |
offentlig IEnumerator GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Oppførsel | Returnerer et nytt sett som er resultatet av foreningens drift av gjeldende og inngangssett. |
| Opptreden | O (mn), hvor m og n er antall gjenstander i henholdsvis angitte og aktuelle sett. |
Foreningen av to sett er et sett som inneholder alle de forskjellige elementene som finnes i begge settene.
For eksempel, gitt to sett (hver representert i rødt):
To inngangssett før foreningens operasjon Når unionsoperasjonen utføres, inneholder utgangssettet alle elementene i begge settene. Hvis det finnes noen elementer som eksisterer i begge settene, blir bare en enkelt kopi av hvert element lagt til utgangssettet.
Utgangssettet sett etter foreningens operasjon (returnerte elementer er gule) Et mer konkret eksempel kan ses når vi forener sammen flere sett med heltall:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
offentlig sett union (sett andre) sett resultat = nytt sett (_items); foreach (T element i other._items) if (! Contains (item)) result.Add (item); returresultat;
| Oppførsel | Returnerer et nytt sett som er resultatet av kryssoperasjonen for gjeldende og inngangssett. |
| Opptreden | O (mn), hvor m og n er antall gjenstander i henholdsvis angitte og aktuelle sett. |
Kryssing er punktet hvor to sett "krysser", for eksempel deres felles medlemmer. Ved hjelp av Venn-diagrammet fra fagforeningen vises krysset mellom de to settene her:
Krysset mellom de to inngangssettene vises i gul Eller bruk sett av heltall:
[1, 2, 3, 4] krysse [3, 4, 5, 6] = [3, 4]
Offentlig Sett Intersection (sett andre) Sett resultat = nytt sett (); foreach (T element i _items) if (other._items.Contains (item)) result.Add (item); returresultat;
| Oppførsel | Returnerer et nytt sett som er resultatet av forskjellen i gjeldende og inngangssett. |
| Opptreden | O (mn), hvor m og n er antall gjenstander i henholdsvis angitte og aktuelle sett. |
Forskjellen, eller sett forskjellen mellom to sett, er elementene som finnes i det første settet (settet hvis Forskjell metoden kalles), men finnes ikke i det andre settet (metodeparameteren). Venn-diagrammet for denne metoden vises her med det returnerte settet i gul:
Den angitte forskjellen mellom to sett Eller bruk sett av heltall:
[1, 2, 3, 4] forskjell [3, 4, 5, 6] = [1, 2]
offentlig sett forskjell (sett andre) sett resultat = nytt sett (_items); foreach (T element i other._items) result.Remove (item); returresultat;
| Oppførsel | Returnerer et nytt sett som er resultatet av den symmetriske forskjellen i gjeldende og inngangssett. |
| Opptreden | O (mn), hvor m og n er antall gjenstander i henholdsvis angitte og aktuelle sett. |
Den symmetriske forskjellen mellom to sett er et sett hvis medlemmer er de elementene som eksisterer i bare ett eller annet sett. Venn-diagrammet for denne metoden vises her med det returnerte settet i gult
Den symmetriske forskjellen på to sett Eller ved hjelp av heltall sett:
[1, 2, 3, 4] symmetrisk forskjell [3, 4, 5, 6] = [1, 2, 5, 6]
Du har kanskje lagt merke til at dette er det motsatte av skjæringsoperasjonen. Med dette i tankene, la oss se hva det ville ta for å finne den symmetriske forskjellen ved å bruke bare de angitte algoritmer vi allerede har sett på.
La oss gå gjennom det vi ønsker.
Vi vil ha et sett som inneholder alle elementene fra begge settene bortsett fra de som finnes i begge. Eller sagt en annen måte, vi vil ha forening av begge settene bortsett fra skjæringspunktet mellom begge settene. Vi ønsker den faste forskjellen mellom foreningen og skjæringspunktet mellom begge settene.
Trinn for trinn ser det slik ut:
[1, 2, 3, 4] union [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] kryss [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] sett forskjell [3, 4] = [1, 2, 5, 6]
Som gir det resulterende settet vi ønsket: ([1, 2, 5, 6]).
offentlig sett symmetrisk forskjell (sett andre) sett union = union (andre); Angi krysset = Intersection (andre); returnere union. Differanse (kryss);
Du lurer kanskje på hvorfor jeg ikke har lagt til en IsSubset metode. Denne typen metode brukes ofte til å avgjøre om et sett er helt inneholdt i et annet sett. For eksempel vil vi kanskje vite om:
[1, 2, 3] er undergruppe [0, 1, 2, 3, 4, 5] = ekte
betraktninger:
[1, 2, 3] er undergruppe [0, 1, 2] = falsk
Grunnen til at jeg ikke har detaljert en IsSubset Metoden er at den kan utføres ved hjelp av eksisterende midler. For eksempel:
[1, 2, 3] forskjell [0, 1, 2, 3, 4, 5] = []
Et tomt resultat sett viser at hele første settet var inneholdt i det andre settet, så vi vet at det første settet er en komplett delmengde av den andre. Et annet eksempel, ved hjelp av krysset:
[1, 2, 3] kryss [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Hvis utgangssettet har samme antall elementer som inngangssettet, vet vi at inngangssettet er en delmengde av det andre settet.
I et generelt formål Sett klasse, ha en IsSubset Metoden kan være nyttig (og kunne implementeres mer optimalt); Jeg ville imidlertid gjøre det poeng at dette ikke nødvendigvis er en ny oppførsel, men bare en annen måte å tenke på eksisterende operasjoner.
