En informática , un conjunto es un tipo de datos abstracto que puede almacenar valores únicos, sin ningún orden particular . Es una implementación informática del concepto matemático de conjunto finito . A diferencia de la mayoría de los otros tipos de colecciones , en lugar de recuperar un elemento específico de un conjunto, normalmente se prueba la pertenencia de un valor a un conjunto.
Algunas estructuras de datos de conjuntos están diseñadas para conjuntos estáticos o congelados que no cambian después de su construcción. Los conjuntos estáticos sólo permiten operaciones de consulta sobre sus elementos, como comprobar si un valor determinado está en el conjunto o enumerar los valores en algún orden arbitrario. Otras variantes, llamadas conjuntos dinámicos o mutables , permiten también la inserción y eliminación de elementos del conjunto.
Un conjunto múltiple es un tipo especial de conjunto en el que un elemento puede aparecer varias veces en el conjunto.
En la teoría de tipos , los conjuntos generalmente se identifican con su función indicadora (función característica): en consecuencia, un conjunto de valores de tipo puede denotarse por o . (Los subtipos y subconjuntos pueden modelarse mediante tipos de refinamiento , y los conjuntos cocientes pueden reemplazarse por setoides ). La función característica de un conjunto se define como:
En teoría, muchas otras estructuras de datos abstractas pueden verse como estructuras establecidas con operaciones adicionales y/o axiomas adicionales impuestos a las operaciones estándar. Por ejemplo, un montón abstracto puede verse como una estructura establecida con una operación que devuelve el elemento de menor valor.min(S)
Se pueden definir las operaciones del álgebra de conjuntos :
union(S,T): devuelve la unión de los conjuntos S y T .intersection(S,T): devuelve la intersección de los conjuntos S y T .difference(S,T): devuelve la diferencia de los conjuntos S y T .subset(S,T): un predicado que prueba si el conjunto S es un subconjunto del conjunto T .Las operaciones típicas que puede proporcionar una estructura de conjunto estático S son:
is_element_of(x,S): comprueba si el valor x está en el conjunto S .is_empty(S): comprueba si el conjunto S está vacío.size(S)o : devuelve el número de elementos en S .cardinality(S)iterate(S): devuelve una función que devuelve un valor más de S en cada llamada, en algún orden arbitrario.enumerate(S): devuelve una lista que contiene los elementos de S en algún orden arbitrario.build(x1,x2,…,xn,): crea una estructura establecida con valores x 1 , x 2 ,..., x n .create_from(collection): crea una nueva estructura de conjunto que contiene todos los elementos de la colección dada o todos los elementos devueltos por el iterador dado .Las estructuras de conjuntos dinámicos suelen agregar:
create(): crea una nueva estructura de conjunto inicialmente vacía.create_with_capacity(n): crea una nueva estructura de conjunto, inicialmente vacía pero capaz de contener hasta n elementos.add(S,x): agrega el elemento x a S , si aún no está presente.remove(S, x): elimina el elemento x de S , si está presente.capacity(S): devuelve el número máximo de valores que S puede contener.Algunas estructuras establecidas pueden permitir sólo algunas de estas operaciones. El coste de cada operación dependerá de la implementación y posiblemente también de los valores particulares almacenados en el conjunto y del orden en que se inserten.
Hay muchas otras operaciones que pueden (en principio) definirse en términos de lo anterior, como por ejemplo:
pop(S): devuelve un elemento arbitrario de S , eliminándolo de S . [1]pick(S): devuelve un elemento arbitrario de S . [2] [3] [4] Funcionalmente, el mutador popse puede interpretar como el par de selectores (pick, rest),donde restdevuelve el conjunto que consta de todos los elementos excepto el elemento arbitrario. [5] Puede interpretarse en términos de iterate. [a]map(F,S): devuelve el conjunto de valores distintos resultantes de aplicar la función F a cada elemento de S .filter(P,S): devuelve el subconjunto que contiene todos los elementos de S que satisfacen un predicado P dado .fold(A0,F,S): devuelve el valor A | S | después de aplicar para cada elemento e de S, para alguna operación binaria F. F debe ser asociativo y conmutativo para que esté bien definido.Ai+1 := F(Ai, e) clear(S): eliminar todos los elementos de S .equal(S1', S2'): comprueba si los dos conjuntos dados son iguales (es decir, contienen todos y sólo los mismos elementos).hash(S): devuelve un valor hash para el conjunto estático S tal que si entoncesequal(S1, S2)hash(S1) = hash(S2)Se pueden definir otras operaciones para conjuntos con elementos de un tipo especial:
sum(S): devuelve la suma de todos los elementos de S para alguna definición de "suma". Por ejemplo, sobre números enteros o reales, se puede definir como .fold(0, add, S)collapse(S): dado un conjunto de conjuntos, devuelve la unión. [6] Por ejemplo, collapse({{1}, {2, 3}}) == {1, 2, 3}. Puede considerarse una especie de sum.flatten(S): dado un conjunto que consta de conjuntos y elementos atómicos (elementos que no son conjuntos), devuelve un conjunto cuyos elementos son los elementos atómicos del conjunto original de nivel superior o elementos de los conjuntos que contiene. En otras palabras, elimine un nivel de anidamiento, collapse,pero permita átomos. Esto se puede hacer una sola vez o aplanando recursivamente para obtener un conjunto de elementos únicamente atómicos. [7] Por ejemplo, flatten({1, {2, 3}}) == {1, 2, 3}.nearest(S,x): devuelve el elemento de S que tiene el valor más cercano a x (según alguna métrica ).min(S), : devuelve el elemento mínimo/máximo de S .max(S)Los conjuntos se pueden implementar utilizando varias estructuras de datos , que proporcionan diferentes compensaciones de tiempo y espacio para diversas operaciones. Algunas implementaciones están diseñadas para mejorar la eficiencia de operaciones muy especializadas, como nearesto union. Las implementaciones descritas como "uso general" normalmente se esfuerzan por optimizar las operaciones element_of, addy . deleteUna implementación sencilla es utilizar una lista , ignorando el orden de los elementos y teniendo cuidado de evitar valores repetidos. Esto es simple pero ineficiente, ya que operaciones como la pertenencia a un conjunto o la eliminación de elementos son O ( n ), ya que requieren escanear toda la lista. [b] En cambio, los conjuntos a menudo se implementan utilizando estructuras de datos más eficientes, particularmente varios tipos de árboles , intentos o tablas hash .
Como los conjuntos pueden interpretarse como una especie de mapa (mediante la función indicadora), los conjuntos se implementan comúnmente de la misma manera que los mapas (parciales) ( matrices asociativas ), en este caso en el que el valor de cada par clave-valor tiene el tipo de unidad o un valor centinela (como 1), es decir, un árbol de búsqueda binario autoequilibrado para conjuntos ordenados [ definición necesaria ] (que tiene O(log n) para la mayoría de las operaciones), o una tabla hash para conjuntos no clasificados (que tiene O(1) caso promedio, pero O(n) peor caso, para la mayoría de las operaciones). Se puede utilizar una tabla hash lineal ordenada [8] para proporcionar conjuntos ordenados de manera determinista.
Además, en lenguajes que admiten mapas pero no conjuntos, los conjuntos se pueden implementar en términos de mapas. Por ejemplo, un modismo de programación común en Perl que convierte una matriz en un hash cuyos valores son el valor centinela 1, para usar como un conjunto, es:
mis %elementos = mapa { $_ => 1 } @elementos ; Otros métodos populares incluyen matrices . En particular, un subconjunto de los números enteros 1.. n se puede implementar de manera eficiente como una matriz de bits de n bits , que también admite operaciones de unión e intersección muy eficientes. Un mapa de Bloom implementa un conjunto de manera probabilística, utilizando una representación muy compacta pero con el riesgo de una pequeña posibilidad de falsos positivos en las consultas.
Las operaciones de conjuntos booleanos se pueden implementar en términos de operaciones más elementales ( pop, cleary add), pero los algoritmos especializados pueden producir límites de tiempo asintóticos más bajos. Si los conjuntos se implementan como listas ordenadas, por ejemplo, el algoritmo ingenuo tomará un tiempo proporcional a la longitud m de S multiplicada por la longitud n de T ; mientras que una variante del algoritmo de fusión de listas hará el trabajo en un tiempo proporcional a m + n . Además, existen estructuras de datos de conjuntos especializadas (como la estructura de datos union-find ) que están optimizadas para una o más de estas operaciones, a expensas de otras.union(S,T)
Uno de los primeros lenguajes que admitió conjuntos fue Pascal ; muchos lenguajes ahora lo incluyen, ya sea en el lenguaje principal o en una biblioteca estándar .
setclase de plantilla, que normalmente se implementa utilizando un árbol de búsqueda binario (por ejemplo, árbol rojo-negro ); El STL de SGIhash_set también proporciona la clase de plantilla, que implementa un conjunto utilizando una tabla hash. C++ 11 admite la unordered_setclase de plantilla, que se implementa mediante una tabla hash. En los conjuntos, los elementos mismos son las claves, a diferencia de los contenedores secuenciados, donde se accede a los elementos utilizando su posición (relativa o absoluta). Los elementos del conjunto deben tener un orden débil estricto.HashSety BTreeSet.Set interfaz para admitir conjuntos (con la HashSetclase implementándolos utilizando una tabla hash) y la SortedSetsubinterfaz para admitir conjuntos ordenados (con la TreeSetclase implementándolos utilizando un árbol de búsqueda binario).NSSet , NSMutableSet,, y . Las API de CoreFoundation proporcionan los tipos CFSet y CFMutableSet para usar en C.NSCountedSetNSOrderedSetNSMutableOrderedSet{x, y, z}; Los conjuntos vacíos deben crearse usando set(), porque Python usa {}para representar el diccionario vacío.HashSety SortedSetque implementan la interfaz genérica ISet.Sety IdentitySet, que utilizan igualdad e identidad para las pruebas de inclusión respectivamente. Muchos dialectos proporcionan variaciones para almacenamiento comprimido ( NumberSet, CharacterSet), para ordenar ( OrderedSet, SortedSet, etc.) o para referencias débiles ( WeakIdentitySet).set incluye un módulo que contiene Setclases SortedSetque implementan conjuntos usando tablas hash, esta última permite la iteración en orden.Set contiene un módulo que implementa una estructura de datos de conjunto funcional utilizando árboles de búsqueda binarios.Data.Setmódulo que implementa conjuntos inmutables utilizando árboles de búsqueda binarios. [9]Settipo, desde Swift 1.2.Setcomo un objeto integrado estándar con el estándar ECMAScript 2015 [10] .sets tiene un módulo.Ada.Containers.Hashed_Setsy Ada.Containers.Ordered_Sets.Como se señaló en la sección anterior, en lenguajes que no admiten conjuntos directamente pero sí admiten matrices asociativas , los conjuntos se pueden emular utilizando matrices asociativas, usando los elementos como claves y usando un valor ficticio como valores, que se ignoran.
Una generalización de la noción de conjunto es la de multiconjunto o bolsa , que es similar a un conjunto pero permite valores repetidos ("iguales") (duplicados). Esto se utiliza en dos sentidos distintos: o los valores iguales se consideran idénticos y simplemente se cuentan, o los valores iguales se consideran equivalentes y se almacenan como elementos distintos. Por ejemplo, dada una lista de personas (por nombre) y edades (en años), se podría construir un conjunto múltiple de edades, que simplemente cuente el número de personas de una edad determinada. Alternativamente, se puede construir un conjunto múltiple de personas, donde dos personas se consideran equivalentes si sus edades son las mismas (pero pueden ser personas diferentes y tener nombres diferentes), en cuyo caso cada par (nombre, edad) debe almacenarse y seleccionar en una edad determinada da a todas las personas de una edad determinada.
Formalmente, es posible que los objetos en informática se consideren "iguales" bajo alguna relación de equivalencia pero aún distintos bajo otra relación. Algunos tipos de implementaciones de conjuntos múltiples almacenarán distintos objetos iguales como elementos separados en la estructura de datos; mientras que otros lo colapsarán a una versión (la primera encontrada) y mantendrán un recuento entero positivo de la multiplicidad del elemento.
Al igual que con los conjuntos, los conjuntos múltiples se pueden implementar naturalmente utilizando tablas hash o árboles, que producen diferentes características de rendimiento.
El conjunto de todas las bolsas sobre el tipo T viene dado por la expresión bolsa T. Si por multiconjunto uno considera idénticos los elementos iguales y simplemente los cuenta, entonces un multiconjunto puede interpretarse como una función desde el dominio de entrada hasta los enteros no negativos ( naturales). números ), generalizando la identificación de un conjunto con su función indicadora. En algunos casos, un conjunto múltiple en este sentido de conteo puede generalizarse para permitir valores negativos, como en Python.
multisetclase para el multiconjunto ordenado, como una especie de contenedor asociativo , que implementa este multiconjunto utilizando un árbol de búsqueda binario autoequilibrado . Proporciona la unordered_multisetclase para el multiconjunto sin ordenar, como una especie de contenedor asociativo desordenado , que implementa este multiconjunto mediante una tabla hash . El conjunto múltiple sin clasificar es estándar a partir de C++11 ; Anteriormente, el STL de SGI proporcionaba la hash_multisetclase, que fue copiada y finalmente estandarizada.Bagy SortedBag, con clases de implementación como HashBagy TreeBag.Multisetinterfaz, con clases de implementación como HashMultisety TreeMultiset.NSCountedSetclase como parte de Cocoa y los tipos CFBagy CFMutableBagcomo parte de CoreFoundation .collections.Counter incluye , que es similar a un conjunto múltiple.Bagclase, de la que se puede crear una instancia para usar identidad o igualdad como predicado para la prueba de inclusión.Cuando no esté disponible una estructura de datos de conjuntos múltiples, una solución alternativa es utilizar un conjunto regular, pero anulando el predicado de igualdad de sus elementos para devolver siempre "no igual" en objetos distintos (sin embargo, estos todavía no podrán almacenar múltiples apariciones de el mismo objeto) o use una matriz asociativa que asigne los valores a sus multiplicidades enteras (esto no podrá distinguir entre elementos iguales en absoluto).
Operaciones típicas sobre bolsas:
contains(B, x): comprueba si el elemento x está presente (al menos una vez) en la bolsa Bis_sub_bag(B1, B2): comprueba si cada elemento de la bolsa B 1 no aparece en B 1 con más frecuencia que en la bolsa B 2 ; a veces denotado como B 1 ⊑ B 2 .count(B, x): devuelve el número de veces que aparece el elemento x en la bolsa B ; a veces se indica como B # x .scaled_by(B, n): dado un número natural n , devuelve una bolsa que contiene los mismos elementos que la bolsa B , excepto que cada elemento que ocurre m veces en B ocurre n * m veces en la bolsa resultante; a veces denotado como n ⊗ B .union(B1, B2): devuelve una bolsa que contiene solo aquellos valores que ocurren en la bolsa B 1 o en la bolsa B 2 , excepto que el número de veces que ocurre un valor x en la bolsa resultante es igual a ( B 1 # x) + ( B 2 # X); a veces denotado como B 1 ⊎ B 2 .En las bases de datos relacionales , una tabla puede ser un conjunto (matemático) o un conjunto múltiple, dependiendo de la presencia de restricciones de unicidad en algunas columnas (lo que la convierte en una clave candidata ).
SQL permite la selección de filas de una tabla relacional: esta operación generalmente producirá un conjunto múltiple, a menos que DISTINCTse use la palabra clave para forzar que las filas sean todas diferentes, o que la selección incluya la clave principal (o candidata).
En ANSI SQL, la MULTISETpalabra clave se puede utilizar para transformar una subconsulta en una expresión de colección:
SELECCIONE expresión1 , expresión2 ... DESDE nombre_tabla ... es una selección general que se puede utilizar como expresión de subconsulta de otra consulta más general, mientras que
MULTISET ( SELECT expresión1 , expresión2 ... FROM nombre_tabla ...) transforma la subconsulta en una expresión de colección que se puede usar en otra consulta o en la asignación a una columna del tipo de colección apropiado.
pickse puede implementar en una clase derivada del integrado setde la siguiente manera:clase Conjunto ( set ): def pick ( self ): regresa siguiente ( iter ( self ))