Share
El Conjunto es un tipo de colección que implementa los algoritmos de conjuntos algebraicos básicos que incluyen unión, intersección, diferencia y diferencia simétrica. Cada uno de estos algoritmos se explicará en detalle en sus respectivas secciones..
Conceptualmente, los conjuntos son colecciones de objetos que a menudo tienen algo en común. Por ejemplo, podríamos tener un conjunto que contenga enteros pares positivos:
[2, 4, 6, 8, 10,…]
Y un conjunto que contiene enteros impares positivos:
[1, 3, 5, 7, 9,…]
Estos dos conjuntos no tienen valores en común. Ahora considera un tercer conjunto que es todos los factores del número 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Dados estos conjuntos, ahora podemos responder la pregunta "¿Qué factores de 100 son impares?" Observando el conjunto de enteros impares y el conjunto de factores de 100 y viendo qué valores existen en ambos conjuntos. Pero también podríamos responder preguntas como "¿Qué números impares no son factores de 100?" O "¿Qué números positivos, pares o impares, no son factores de 100?"
Esto puede no parecer muy útil, pero eso es porque el ejemplo es algo artificial. Imagínese si los grupos fueran todos los empleados de una empresa y todos los empleados que habían completado la capacitación anual obligatoria..
Podríamos responder fácilmente a la pregunta: "¿Qué empleados no han completado la capacitación obligatoria?"
Podemos continuar agregando conjuntos y comenzar a responder preguntas muy complejas como, por ejemplo, "¿Qué empleados de tiempo completo en el equipo de ventas a los que se ha emitido una tarjeta de crédito corporativa no han asistido a la capacitación obligatoria sobre el nuevo proceso de informe de gastos?"
los Conjunto clase implementa el Enumerable interfaz y acepta un argumento genérico que debería ser una Incomparables tipo (es necesario probar la igualdad para que funcionen los algoritmos establecidos).
Los miembros del conjunto estarán contenidos en un .NET. Lista clase, pero en la práctica, los conjuntos a menudo están contenidos en estructuras de árbol como un árbol de búsqueda binario. Esta elección del contenedor subyacente afecta la complejidad de los diversos algoritmos. Por ejemplo, usando el Lista, Contiene tiene una complejidad de O (n), mientras que usar un árbol resultaría en O (log n) en promedio.
Además de los métodos que implementaremos, el Conjunto incluye un constructor por defecto y uno que acepta un Enumerable de elementos para poblar el conjunto con.
conjunto de clases públicas: IEnumerable donde T: IComparable Lista privada de solo lectura _items = new List (); public Set () public Set (IEnumerable items) AddRange (items); public void Add (elemento T); public void AddRange (IEnumerable items); public bool Remove (artículo T); Contiene bool public (elemento T); public int Count get; conjunto público de unión (otro conjunto); Intersección de conjuntos públicos (otro conjunto); Diferencia de conjunto público (otro conjunto); conjunto público SymmetricDifference (otro conjunto); public IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Comportamiento | Agrega el artículo al conjunto. Si el elemento ya existe en el conjunto, se lanza una InvalidOperationException. |
| Actuación | En) |
Al implementar el Añadir Algoritmo, se debe tomar una decisión: ¿permitirá el conjunto elementos duplicados o no? Por ejemplo, dado el siguiente conjunto:
[1, 2, 3, 4]
Si la persona que llama intenta agregar el valor tres, el conjunto se convertirá en:
[1, 2, 3, 3, 4]
Si bien esto podría ser aceptable en algunos contextos, no es el comportamiento que vamos a implementar. Imagina un conjunto que contenga a todos los estudiantes en una universidad local. No sería lógico permitir que el mismo alumno se agregue dos veces al conjunto. De hecho, intentar hacerlo es probablemente un error (y será tratado como tal en esta implementación).
Nota: Añadir utiliza el Contiene Método
Accentsconagua
public void Add (T item) if (Contiene (item)) lanza una nueva InvalidOperationException ("El item ya existe en Set"); _items.Add (item); | Comportamiento | Agrega varios elementos al conjunto. Si algún miembro del enumerador de entrada existe en el conjunto, o si hay elementos duplicados en el enumerador de entrada, se lanzará una InvalidOperationException. |
| Actuación | O (mn), donde m es el número de elementos en la enumeración de entrada y n es el número de elementos actualmente en el conjunto. |
public void AddRange (IEnumerable items) foreach (T item en items) Add (item);
| Comportamiento | Elimina el valor especificado del conjunto si lo encuentra, devolviendo verdadero. Si el conjunto no contiene el valor especificado, se devuelve falso. |
| Actuación | En) |
public bool Remove (T item) return _items.Remove (item);
| Comportamiento | Devuelve verdadero si el conjunto contiene el valor especificado. De lo contrario, devuelve falso.. |
| Actuación | En) |
public bool Contains (T item) return _items.Contains (item);
| Comportamiento | Devuelve el número de elementos en el conjunto o 0 si el conjunto está vacío. |
| Actuación | O (1) |
public int Count get return _items.Count;
| Comportamiento | Devuelve un enumerador para todos los elementos del conjunto.. |
| Actuación | O (1) para devolver el enumerador. Enumerar todos los elementos tiene una complejidad de O (n). |
public IEnumerator GetEnumerator () return _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return _items.GetEnumerator ();
| Comportamiento | Devuelve un nuevo conjunto que es el resultado de la operación de unión del conjunto actual y de entrada. |
| Actuación | O (mn), donde m y n son el número de elementos en los conjuntos proporcionados y actuales, respectivamente. |
La unión de dos conjuntos es un conjunto que contiene todos los elementos distintos que existen en ambos conjuntos.
Por ejemplo, dados dos conjuntos (cada uno representado en rojo):
Dos entradas antes de la operación de unión. Cuando se realiza la operación de unión, el conjunto de salida contiene todos los elementos en ambos conjuntos. Si hay elementos que existen en ambos conjuntos, solo se agrega una copia de cada elemento al conjunto de salida.
El conjunto de salida después de la operación de unión (los elementos devueltos son amarillos) Se puede ver un ejemplo más concreto cuando unimos varios conjuntos de enteros:
[1, 2, 3, 4] Unión [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
unión de conjuntos públicos (otro conjunto) Set result = new Set (_items); foreach (T item en other._items) if (! Contiene (item)) result.Add (item); devolver el resultado;
| Comportamiento | Devuelve un nuevo conjunto que es el resultado de la operación de intersección de los conjuntos actuales y de entrada. |
| Actuación | O (mn), donde m y n son el número de elementos en los conjuntos proporcionados y actuales, respectivamente. |
La intersección es el punto en el que dos conjuntos "se intersecan", por ejemplo, sus miembros comunes. Usando el diagrama de Venn del ejemplo de unión, la intersección de los dos conjuntos se muestra aquí:
La intersección de los dos conjuntos de entrada se muestra en amarillo O bien, utilizando conjuntos de enteros:
[1, 2, 3, 4] intersecarse [3, 4, 5, 6] = [3, 4]
Intersección de conjuntos públicos (otros conjuntos) Set result = new Set (); foreach (T item en _items) if (other._items.Contains (item)) result.Add (item); devolver el resultado;
| Comportamiento | Devuelve un nuevo conjunto que es el resultado de la operación de diferencia de los conjuntos actuales y de entrada. |
| Actuación | O (mn), donde m y n son el número de elementos en los conjuntos proporcionados y actuales, respectivamente. |
La diferencia, o diferencia de conjunto, entre dos conjuntos es los elementos que existen en el primer conjunto (el conjunto cuyos Diferencia se está llamando al método), pero no existe en el segundo conjunto (el parámetro del método). El diagrama de Venn para este método se muestra aquí con el conjunto devuelto en amarillo:
La diferencia de conjuntos entre dos conjuntos. O bien, utilizando conjuntos de enteros:
[1, 2, 3, 4] diferencia [3, 4, 5, 6] = [1, 2]
Diferencia de conjunto público (otro conjunto) Establecer resultado = nuevo conjunto (_items); foreach (T item en other._items) result.Remove (item); resultado de retorno;
| Comportamiento | Devuelve un nuevo conjunto que es el resultado de la operación de diferencia simétrica de los conjuntos actuales y de entrada. |
| Actuación | O (mn), donde m y n son el número de elementos en los conjuntos proporcionados y actuales, respectivamente. |
La diferencia simétrica de dos conjuntos es un conjunto cuyos miembros son aquellos elementos que existen solo en uno u otro conjunto. El diagrama de Venn para este método se muestra aquí con el conjunto devuelto en amarillo
La diferencia simétrica de dos conjuntos. O, usando conjuntos de enteros:
[1, 2, 3, 4] diferencia simétrica [3, 4, 5, 6] = [1, 2, 5, 6]
Es posible que haya notado que esto es exactamente lo contrario de la operación de intersección. Con esto en mente, veamos qué se necesita para encontrar la diferencia simétrica utilizando solo los algoritmos establecidos que ya hemos analizado.
Caminemos por lo que queremos.
Queremos un conjunto que contenga todos los elementos de ambos conjuntos excepto aquellos que existen en ambos. O dicho de otra manera, queremos la unión de ambos conjuntos a excepción de la intersección de ambos conjuntos. Queremos la diferencia de conjunto entre la unión y la intersección de ambos conjuntos..
Paso a paso, se ve así:
[1, 2, 3, 4] Unión [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] intersección [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] establecer diferencia [3, 4] = [1, 2, 5, 6]
Lo que da el conjunto resultante que queríamos: ([1, 2, 5, 6]).
conjunto público SymmetricDifference (otro conjunto) Set union = Union (otro); Establecer intersección = Intersección (otro); volver union.Diferencia (interseccion);
Quizás se pregunte por qué no agregué un IsSubset método. Este tipo de método se usa comúnmente para determinar si un conjunto está completamente contenido en otro conjunto. Por ejemplo, podríamos querer saber si:
[1, 2, 3] es subconjunto [0, 1, 2, 3, 4, 5] = cierto
Mientras:
[1, 2, 3] es subconjunto [0, 1, 2] = falso
La razón por la que no he detallado una IsSubset El método es que se puede realizar utilizando los medios existentes. Por ejemplo:
[1, 2, 3] diferencia [0, 1, 2, 3, 4, 5] = []
Un conjunto de resultados vacío muestra que todo el primer conjunto estaba contenido en el segundo conjunto, por lo que sabemos que el primer conjunto es un subconjunto completo del segundo. Otro ejemplo, usando la intersección:
[1, 2, 3] intersección [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Si el conjunto de salida tiene el mismo número de elementos que el conjunto de entrada, sabemos que el conjunto de entrada es un subconjunto del segundo conjunto.
En una clase Set de propósito general, tener un IsSubset El método podría ser útil (y podría implementarse de manera más óptima); sin embargo, quería señalar que esto no es necesariamente un comportamiento nuevo, sino más bien otra forma de pensar acerca de las operaciones existentes.
