Conjunto (tipo de datos abstracto)

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 un 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 solo permiten operaciones de consulta sobre sus elementos, como verificar si un valor dado está en el conjunto o enumerar los valores en un orden arbitrario. Otras variantes, llamadas conjuntos dinámicos o mutables , también permiten la inserción y eliminación de elementos del conjunto.

Un multiconjunto 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 se identifican generalmente 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 por tipos de refinamiento , y los conjuntos cocientes pueden reemplazarse por setoides ). La función característica de un conjunto se define como: ${\estilo de visualización A}$${\estilo de visualización 2^{A}}$${\displaystyle {\mathcal {P}}(A)}$${\estilo de visualización F}$${\estilo de visualización S}$

${\displaystyle F(x)={\begin{cases}1,&{\mbox{si }}x\en S\\0,&{\mbox{si }}x\no \en S\end{cases}}}$

En teoría, muchas otras estructuras de datos abstractas pueden considerarse como estructuras de conjunto con operaciones adicionales y/o axiomas adicionales impuestos a las operaciones estándar. Por ejemplo, un montón abstracto puede considerarse como una estructura de conjunto 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ática 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 un orden arbitrario.
• enumerate(S): devuelve una lista que contiene los elementos de S en un orden arbitrario.
• build(x1,x2,…,xn,): crea una estructura de conjunto con valores x ₁ , x ₂ ,..., 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 generalmente agregan:

• 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 albergar 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 de conjuntos pueden permitir solo algunas de estas operaciones. El costo 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, tales como:

• 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 poppuede interpretarse como el par de selectores (pick, rest),donde restdevuelve el conjunto que consiste en 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 dado P.
• fold(A0,F,S): devuelve el valor A _{| S |} después de aplicar para cada elemento e de S, alguna operación binaria F. F debe ser asociativa y conmutativa para que esté bien definida.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, puede definirse 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 un tipo 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 de nivel superior original o elementos de los conjuntos que contiene. En otras palabras, elimina un nivel de anidación, como collapse,pero permite átomos. Esto se puede hacer una sola vez o aplanando recursivamente para obtener un conjunto de solo elementos atómicos. ^[7] Por ejemplo, flatten({1, {2, 3}}) == {1, 2, 3}.
• nearest(S,x): devuelve el elemento de S que tiene un 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 varias operaciones. Algunas implementaciones están diseñadas para mejorar la eficiencia de operaciones muy especializadas, como nearesto union. Las implementaciones descritas como de "uso general" normalmente intentan optimizar las operaciones element_of, addy delete. Una implementación simple es utilizar una lista , ignorando el orden de los elementos y teniendo cuidado de evitar valores repetidos. Esto es simple pero ineficiente, ya que las operaciones como la pertenencia a un conjunto o la eliminación de elementos son O ( n ), ya que requieren escanear la lista completa. ^[b] Los conjuntos a menudo se implementan utilizando estructuras de datos más eficientes, en particular varios tipos de árboles , intentos o tablas hash .

Como los conjuntos pueden interpretarse como una especie de mapa (por 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 ordenados (que tiene O(1) caso promedio, pero O(n) peor caso, para la mayoría de las operaciones). Una tabla hash lineal ordenada ^[8] puede usarse para proporcionar conjuntos ordenados determinísticamente.

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 su uso como 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 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 un pequeño riesgo de falsos positivos en las consultas.

Las operaciones de conjuntos booleanos se pueden implementar en términos de operaciones más elementales ( pop, clear, y 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 para tomará un tiempo proporcional a la longitud m de S 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 de unión-búsqueda ) 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 ; ahora muchos lenguajes lo incluyen, ya sea en el lenguaje principal o en una biblioteca estándar .

• En C++ , la biblioteca de plantillas estándar (STL) proporciona la setclase de plantilla, que normalmente se implementa utilizando un árbol de búsqueda binario (por ejemplo, árbol rojo-negro ); la STL de SGIhash_set también proporciona la clase de plantilla, que implementa un conjunto utilizando una tabla hash. C++11 tiene soporte para la unordered_setclase de plantilla, que se implementa utilizando una tabla hash. En los conjuntos, los elementos mismos son las claves, en contraste con 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.
• La biblioteca estándar de Rust proporciona los tipos genéricos HashSety BTreeSet.
• Java ofrece la Set interfaz para soportar conjuntos (con la HashSetclase implementándola usando una tabla hash) y la SortedSetsubinterfaz para soportar conjuntos ordenados (con la TreeSetclase implementándola usando un árbol de búsqueda binaria).
• El marco Foundation de Apple (parte de Cocoa ) proporciona las clases Objective-CNSSet , NSMutableSet, NSCountedSet, NSOrderedSet, y NSMutableOrderedSet. Las API CoreFoundation proporcionan los tipos CFSet y CFMutableSet para usar en C .
• Python tiene tipos de conjuntos y conjuntos congelados incorporados desde 2.4, y desde Python 3.0 y 2.7, admite literales de conjuntos no vacíos utilizando una sintaxis de llaves, por ejemplo: {x, y, z}; los conjuntos vacíos deben crearse utilizando set(), porque Python utiliza {}para representar el diccionario vacío.
• .NET Framework proporciona las clases genéricas HashSety SortedSetque implementan la ISetinterfaz genérica.
• La biblioteca de clases de SmalltalkSet incluye y IdentitySet, que utilizan igualdad e identidad para la prueba de inclusión respectivamente. Muchos dialectos proporcionan variaciones para almacenamiento comprimido ( NumberSet, CharacterSet), para ordenamiento ( OrderedSet, SortedSet, etc.) o para referencias débiles ( WeakIdentitySet).
• La biblioteca estándar de Rubyset incluye un módulo que contiene Setclases SortedSetque implementan conjuntos utilizando tablas hash, estas últimas permitiendo la iteración en orden ordenado.
• La biblioteca estándar de OCamlSet contiene un módulo que implementa una estructura de datos de conjunto funcional utilizando árboles de búsqueda binaria.
• La implementación GHC de Haskell proporciona un Data.Setmódulo que implementa conjuntos inmutables utilizando árboles de búsqueda binaria. ^[9]
• El paquete Tcl Tcllib proporciona un módulo de conjunto que implementa una estructura de datos de conjunto basada en listas TCL.
• La biblioteca estándar de Swift contiene un Settipo, desde Swift 1.2.
• JavaScript se introdujo Setcomo un objeto integrado estándar con el estándar ECMAScript 2015 ^[10] .
• La biblioteca estándar de Erlangsets tiene un módulo.
• Clojure tiene una sintaxis literal para conjuntos hash y también implementa conjuntos ordenados.
• LabVIEW tiene soporte nativo para conjuntos, desde la versión 2019.
• Ada proporciona los paquetes 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í matrices asociativas , los conjuntos se pueden emular usando matrices asociativas, utilizando los elementos como claves y 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 bien los valores iguales se consideran idénticos y simplemente se cuentan, o bien 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 multiconjunto de edades, que simplemente cuenta el número de personas de una edad dada. Alternativamente, se puede construir un multiconjunto 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 la selección de una edad dada da todas las personas de una edad dada.

Formalmente, es posible que los objetos en informática se consideren "iguales" bajo alguna relación de equivalencia , pero que sean distintos bajo otra relación. Algunos tipos de implementaciones de conjuntos múltiples almacenarán objetos iguales distintos como elementos separados en la estructura de datos, mientras que otros los reducirán a una sola versión (la primera que se encuentre) y mantendrán un recuento entero positivo de la multiplicidad del elemento.

Al igual que con los conjuntos, los multiconjuntos 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 se consideran idénticos los elementos iguales y simplemente se cuentan, entonces un multiconjunto puede interpretarse como una función del dominio de entrada a los enteros no negativos ( números naturales ), generalizando la identificación de un conjunto con su función indicadora. En algunos casos un multiconjunto en este sentido de conteo puede generalizarse para permitir valores negativos, como en Python.

• La biblioteca de plantillas estándar de C++ implementa conjuntos múltiples ordenados y no ordenados. Proporciona la multisetclase para el conjunto múltiple ordenado, como una especie de contenedor asociativo , que implementa este conjunto múltiple utilizando un árbol binario de búsqueda autoequilibrado . Proporciona la unordered_multisetclase para el conjunto múltiple no ordenado, como una especie de contenedor asociativo no ordenado , que implementa este conjunto múltiple utilizando una tabla hash . El conjunto múltiple no ordenado es estándar a partir de C++11 ; anteriormente, la STL de SGI proporcionaba la hash_multisetclase, que fue copiada y finalmente estandarizada.
• Para Java , las bibliotecas de terceros proporcionan funcionalidad multiconjunto:
  • Apache Commons Collections proporciona las interfaces Bagy SortedBag, con clases de implementación como HashBagy TreeBag.
  • Google Guava proporciona la Multisetinterfaz, con clases de implementación como HashMultisety TreeMultiset.
• Apple proporciona la NSCountedSetclase como parte de Cocoa y los CFBagtipos CFMutableBagy como parte de CoreFoundation .
• La biblioteca estándar de Pythoncollections.Counter incluye , que es similar a un multiconjunto.
• Smalltalk incluye la Bagclase, que puede instanciarse para usar identidad o igualdad como predicado para la prueba de inclusión.

Cuando no está disponible una estructura de datos de múltiples conjuntos, una solución alternativa es utilizar un conjunto regular, pero anular el predicado de igualdad de sus elementos para que siempre devuelva "no igual" en objetos distintos (sin embargo, esto aún no podrá almacenar múltiples ocurrencias del mismo objeto) o utilizar una matriz asociativa que asigne los valores a sus multiplicidades enteras (esto no podrá distinguir entre elementos iguales en absoluto).

Operaciones típicas en bolsas:

• contains(B, x): comprueba si el elemento x está presente (al menos una vez) en la bolsa B
• is_sub_bag(B1, B2): comprueba si cada elemento de la bolsa B ₁ aparece en B ₁ no más a menudo que en la bolsa B ₂ ; a veces se denota como B ₁ ⊑ B ₂ .
• count(B, x): devuelve el número de veces que el elemento x aparece en la bolsa B ; a veces se denota 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 aparece m veces en B aparece n * m veces en la bolsa resultante; a veces se denota como n ⊗ B .
• union(B1, B2): devuelve una bolsa que contiene solo aquellos valores que aparecen en la bolsa B ₁ o en la bolsa B ₂ , excepto que el número de veces que aparece un valor x en la bolsa resultante es igual a ( B ₁ # x) + ( B ₂ # x); a veces se denota como B ₁ ⊎ B ₂ .

En las bases de datos relacionales , una tabla puede ser un conjunto (matemático) o un multiconjunto, 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 en general producirá un conjunto múltiple, a menos que DISTINCTse use la palabra clave para forzar que las filas sean todas diferentes, o la selección incluya la clave principal (o una clave candidata).

En ANSI SQL, la MULTISETpalabra clave se puede utilizar para transformar una subconsulta en una expresión de colección:

SELECCIONAR expresión1 , expresión2 ... DE 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 puede usarse en otra consulta o en la asignación a una columna del tipo de colección apropiado.

• Filtro Bloom
• Conjunto disjunto
• Conjunto (matemáticas)