Share
Il Set è un tipo di raccolta che implementa gli algoritmi di base algebrici inclusi unione, intersezione, differenza e differenza simmetrica. Ognuno di questi algoritmi verrà spiegato in dettaglio nelle rispettive sezioni.
Concettualmente, gli insiemi sono raccolte di oggetti che spesso hanno alcuni punti in comune. Ad esempio, potremmo avere un set che contiene interi positivi anche:
[2, 4, 6, 8, 10, ...]
E un set che contiene numeri interi dispari positivi:
[1, 3, 5, 7, 9, ...]
Questi due set non hanno valori in comune. Ora considera un terzo set che è tutti i fattori del numero 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Dati questi set, ora possiamo rispondere alla domanda "Quali fattori di 100 sono dispari?" Osservando l'insieme di interi dispari e l'insieme di fattori di 100 e vedendo quali valori esistono in entrambi gli insiemi. Ma potremmo anche rispondere a domande come "Quali numeri dispari non sono fattori di 100?" O "Quali numeri positivi, pari o dispari, non sono fattori di 100?"
Questo potrebbe non sembrare molto utile, ma è perché l'esempio è un po 'forzato. Immagina se i set fossero tutti i dipendenti di un'azienda e tutti i dipendenti che avevano completato la formazione annuale obbligatoria.
Potremmo facilmente rispondere alla domanda "Quali impiegati non hanno completato la formazione obbligatoria?"
Possiamo continuare ad aggiungere serie aggiuntive e iniziare a rispondere a domande molto complesse come "Quali dipendenti a tempo pieno del team di vendita che hanno emesso una carta di credito aziendale non hanno partecipato alla formazione obbligatoria sul nuovo processo di reporting spese?"
Il Impostato la classe implementa il IEnumerable interfaccia e accetta un argomento generico che dovrebbe essere un IComparable tipo (il test per l'uguaglianza è necessario affinché gli algoritmi impostati funzionino).
I membri del set saranno contenuti in un .NET Elenco classe, ma in pratica, gli insiemi sono spesso contenuti in strutture ad albero come un albero di ricerca binario. Questa scelta del contenitore sottostante influisce sulla complessità dei vari algoritmi. Ad esempio, utilizzando il Elenco, contiene ha una complessità di O (n), mentre usando un albero risulterebbe in O (log n) in media.
Oltre ai metodi che implementeremo, il Impostato include un costruttore predefinito e uno che accetta un IEnumerable di elementi per popolare l'insieme con.
public class Set: IEnumerable where T: IComparable elenco readonly privato _items = new List (); public Set () public Set (elementi IEnumerable) AddRange (items); pubblico vuoto Aggiungi (elemento T); vuoto pubblico AddRange (elementi IEnumerable); bool pubblico Rimuovi (elemento T); bool pubblico Contiene (elemento T); int pubblico count; public Set Union (Set altro); pubblico Imposta intersezione (Imposta altro); pubblico Imposta Differenza (Imposta altro); public Set SymmetricDifference (Set other); IEnumerator pubblico GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Comportamento | Aggiunge l'elemento al set. Se l'elemento esiste già nel set, viene generata un'eccezione InvalidOperationException. |
| Prestazione | Sopra) |
Quando si implementa il Inserisci Algoritmo, una decisione deve essere presa: il set consentirà o meno gli elementi duplicati? Ad esempio, dato il seguente set:
[1, 2, 3, 4]
Se il chiamante tenta di aggiungere il valore tre, il set diventerà:
[1, 2, 3, 3, 4]
Sebbene ciò possa essere accettabile in alcuni contesti, non è il comportamento che implementeremo. Immagina un set che contenga tutti gli studenti di un college locale. Non sarebbe logico consentire allo stesso studente di essere aggiunto al set due volte. In realtà, tentare di farlo è probabilmente un errore (e sarà trattato come tale in questa implementazione).
Nota: Aggiungi usa il contiene Metodo
Accentsconagua
pubblico vuoto Aggiungi (elemento T) if (Contains (item)) lancia nuova InvalidOperationException ("L'elemento esiste già nel Set"); _items.Add (elemento); | Comportamento | Aggiunge più elementi al set. Se nell'insieme è presente un membro dell'enumeratore di input o se nell'enumeratore di input sono presenti elementi duplicati, verrà generata un'eccezione InvalidOperationException. |
| Prestazione | O (mn), dove m è il numero di elementi nell'enumerazione di input e n è il numero di elementi attualmente nel set. |
public void AddRange (IEnumerable items) foreach (T item in items) Aggiungi (elemento);
| Comportamento | Rimuove il valore specificato dall'insieme se trovato, restituendo true. Se il set non contiene il valore specificato, viene restituito false. |
| Prestazione | Sopra) |
public bool Remove (T item) return _items.Remove (item);
| Comportamento | Restituisce true se il set contiene il valore specificato. Altrimenti restituisce falso. |
| Prestazione | Sopra) |
bool pubblico Contiene (elemento T) return _items.Contains (item);
| Comportamento | Restituisce il numero di elementi nel set o 0 se il set è vuoto. |
| Prestazione | O (1) |
public int Count get return _items.Count;
| Comportamento | Restituisce un enumeratore per tutti gli elementi nel set. |
| Prestazione | O (1) per restituire l'enumeratore. L'enumerazione di tutti gli elementi ha una complessità di O (n). |
public IEnumerator GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Comportamento | Restituisce un nuovo set che è il risultato dell'operazione union del set corrente e di input. |
| Prestazione | O (mn), dove m e n sono rispettivamente il numero di elementi nei set forniti e correnti. |
L'unione di due set è un set che contiene tutti gli elementi distinti che esistono in entrambi i set.
Ad esempio, dati due set (ciascuno rappresentato in rosso):
Due set di input prima dell'operazione di unione Quando viene eseguita l'operazione di unione, il set di output contiene tutti gli elementi in entrambi i set. Se ci sono elementi che esistono in entrambi i set, solo una singola copia di ogni articolo viene aggiunta al set di output.
L'output impostato dopo l'operazione di unione (gli articoli restituiti sono gialli) Un esempio più concreto può essere visto quando uniamo insieme più insiemi di numeri interi:
[1, 2, 3, 4] unione [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (Set other) Set result = new Set (_items); foreach (T item in other._items) if (! Contains (item)) result.Add (item); restituisce il risultato;
| Comportamento | Restituisce un nuovo set che è il risultato dell'operazione di intersezione dei set corrente e di input. |
| Prestazione | O (mn), dove m e n sono rispettivamente il numero di elementi nei set forniti e correnti. |
L'intersezione è il punto in cui due insiemi "intersecano", ad esempio i loro membri comuni. Usando il diagramma di Venn dall'esempio dell'unione, l'intersezione dei due gruppi è mostrata qui:
L'intersezione dei due set di input è mostrata in giallo Oppure, usando insiemi di numeri interi:
[1, 2, 3, 4] intersecare [3, 4, 5, 6] = [3, 4]
public Set Intersection (Set other) Set result = new Set (); foreach (T item in _items) if (other._items.Contains (item)) result.Add (item); restituisce il risultato;
| Comportamento | Restituisce un nuovo set che è il risultato dell'operazione di differenza dei set corrente e di input. |
| Prestazione | O (mn), dove m e n sono rispettivamente il numero di elementi nei set forniti e correnti. |
La differenza, o differenza di set, tra due set è quella che esiste nel primo set (l'insieme di cui Differenza viene chiamato il metodo), ma non esistono nel secondo set (parametro del metodo). Il diagramma di Venn per questo metodo è mostrato qui con il set restituito in giallo:
La differenza tra due set Oppure, usando insiemi di numeri interi:
[1, 2, 3, 4] differenza [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); risultato di ritorno;
| Comportamento | Restituisce un nuovo set che è il risultato dell'operazione di differenza simmetrica dei set corrente e di input. |
| Prestazione | O (mn), dove m e n sono rispettivamente il numero di elementi nei set forniti e correnti. |
La differenza simmetrica di due set è un set i cui membri sono quegli elementi che esistono solo nell'uno o nell'altro insieme. Il diagramma di Venn per questo metodo è mostrato qui con il set restituito in giallo
La differenza simmetrica di due set Oppure, utilizzando i set di interi:
[1, 2, 3, 4] differenza simmetrica [3, 4, 5, 6] = [1, 2, 5, 6]
Potresti aver notato che questo è l'esatto opposto dell'operazione di intersezione. Con questo in mente, vediamo cosa sarebbe necessario per trovare la differenza simmetrica usando solo gli algoritmi impostati che abbiamo già visto.
Passiamo attraverso ciò che vogliamo.
Vogliamo un set che contenga tutti gli elementi di entrambi i set ad eccezione di quelli esistenti in entrambi. O detto in un altro modo, vogliamo l'unione di entrambi gli insiemi tranne l'intersezione di entrambi gli insiemi. Vogliamo la differenza tra l'unione e l'intersezione di entrambi gli insiemi.
Passo dopo passo, assomiglia a questo:
[1, 2, 3, 4] unione [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] intersezione [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] imposta la differenza [3, 4] = [1, 2, 5, 6]
Quale produce il set risultante che volevamo: ([1, 2, 5, 6]).
public Set SymmetricDifference (Set other) Set union = Union (altro); Imposta intersezione = Intersezione (altro); return union.Difference (intersezione);
Ti starai chiedendo perché non l'ho aggiunto IsSubset metodo. Questo tipo di metodo è comunemente usato per determinare se un set è interamente contenuto in un altro set. Ad esempio, potremmo voler sapere se:
[1, 2, 3] è sottoinsieme [0, 1, 2, 3, 4, 5] = vero
Mentre:
[1, 2, 3] è sottoinsieme [0, 1, 2] = falso
La ragione per cui non ho dettagliato un IsSubset il metodo è che può essere eseguito usando mezzi esistenti. Per esempio:
[1, 2, 3] differenza [0, 1, 2, 3, 4, 5] = []
Un set di risultati vuoto mostra che l'intero primo set era contenuto nel secondo set, quindi sappiamo che il primo set è un sottoinsieme completo del secondo. Un altro esempio, utilizzando l'intersezione:
[1, 2, 3] intersezione [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Se il set di output ha lo stesso numero di elementi del set di input, sappiamo che il set di input è un sottoinsieme del secondo set.
In una classe Set per scopi generali, avendo un IsSubset il metodo potrebbe essere utile (e potrebbe essere implementato in modo più ottimale); tuttavia, volevo sottolineare che questo non è necessariamente un nuovo comportamento, ma piuttosto un altro modo di pensare alle operazioni esistenti.
