Conjunto (tipo de dato abstracto)

En informática , un conjunto es un tipo de dato abstracto que puede almacenar valores distintos, sin ningún orden en particular . Es una implementación informática del concepto matemático de conjunto finito . A diferencia de la mayoría de los demás tipos de colecciones , en lugar de recuperar un elemento específico de un conjunto, normalmente se comprueba si un valor pertenece a él.

Algunas estructuras de datos de conjuntos están diseñadas para conjuntos estáticos o fijos que no cambian después de su creación. Los conjuntos estáticos solo permiten operaciones de consulta sobre sus elementos, como comprobar si un valor dado pertenece al conjunto o enumerar los valores en un orden arbitrario. Otras variantes, denominadas conjuntos dinámicos o mutables , permiten además la inserción y eliminación de elementos.

Un multiconjunto es un tipo especial de conjunto en el que un elemento puede aparecer varias veces.

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${\displaystyle A}$puede denotarse por${\displaystyle 2^{A}}$o${\displaystyle {\mathcal {P}}(A)}$(Los subtipos y subconjuntos pueden modelarse mediante tipos de refinamiento , y los conjuntos cociente pueden reemplazarse por setoides ). La función característica${\displaystyle F}$de un conjunto${\displaystyle S}$se define como:

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

En teoría, muchas otras estructuras de datos abstractas pueden considerarse estructuras de conjuntos con operaciones adicionales o axiomas adicionales impuestos a las operaciones estándar. Por ejemplo, un montón abstracto puede considerarse una estructura de conjuntos con una operación que devuelve el elemento de menor valor.min(S)

Los conjuntos se pueden implementar utilizando diversas 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 de "uso general" suelen esforzarse por optimizar las operaciones element_of, add, y delete. Una implementación simple es usar 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 ]} Los conjuntos a menudo se implementan utilizando estructuras de datos más eficientes, en particular varios tipos de árboles , tries o tablas hash .

Como los conjuntos pueden interpretarse como una especie de mapa (mediante la función indicadora), se suelen implementar de la misma forma que los mapas (parciales) ( arreglos asociativos ) –en este caso, donde 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 binaria autoequilibrado para conjuntos ordenados (que tiene O(log n) para la mayoría de las operaciones), o una tabla hash para conjuntos no ordenados (que tiene O(1) en el caso promedio, pero O(n) en el peor de los casos, para la mayoría de las operaciones). Se puede utilizar una tabla hash lineal ordenada ^{[ 8 ] para proporcionar conjuntos ordenados de forma 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 un array en un hash cuyos valores son el valor centinela 1, para usarlo como un conjunto, es:

mis %elementos = mapa { $_ => 1 } @elementos ;

Otros métodos populares incluyen los arreglos . En particular, un subconjunto de los enteros del 1 al n se puede implementar de manera eficiente como un arreglo 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 forma 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 pueden implementarse 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 en admitir conjuntos fue Pascal ; muchos lenguajes ahora lo incluyen, ya sea en el lenguaje base o en una biblioteca estándar .

• En C++ , la Biblioteca de Plantillas Estándar (STL) proporciona la setclase de plantilla, que normalmente se implementa mediante un árbol de búsqueda binaria (por ejemplo, un árbol rojo-negro ); la STL de SGIhash_set también proporciona la clase de plantilla, que implementa un conjunto mediante 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 mediante su posición (relativa o absoluta). Los elementos de un conjunto deben tener un orden débil estricto.
• La biblioteca estándar de Rust proporciona los tipos genéricos HashSety .BTreeSet
• Java ofrece la Setinterfaz para admitir conjuntos (con la HashSetclase que la implementa utilizando una tabla hash) y la SortedSetsubinterfaz para admitir conjuntos ordenados (con la TreeSetclase que la implementa utilizando un árbol de búsqueda binaria).
• El framework Foundation de Apple (parte de Cocoa ) proporciona las clases Objective-CNSSet , NSMutableSet, NSCountedSet, NSOrderedSet, y NSMutableOrderedSet. Las API de CoreFoundation proporcionan los tipos CFSet y CFMutableSet para su uso en C.
• Python tiene settiposfrozenset incorporados desde la versión 2.4, y desde Python 3.0 y 2.7, admite literales de conjuntos no vacíos usando una sintaxis de llaves, por ejemplo: {x, y, z}; los conjuntos vacíos deben crearse usando set(), porque Python usa {}para representar el diccionario vacío.
• El .NET Framework proporciona las clases genéricas HashSetque SortedSetimplementan la ISetinterfaz genérica.
• La biblioteca de clases de SmalltalkSet incluye y IdentitySet, utilizando 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, lo que permite 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 de Haskell en GHC proporciona un módulo que implementa conjuntos inmutables utilizando árboles de búsqueda binaria. ^{[ 9 ]}Data.Set
• El paquete Tcllib de Tcl proporciona un módulo de conjuntos que implementa una estructura de datos de conjuntos basada en listas de TCL.
• La biblioteca estándar de SwiftSet contiene un tipo, 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 ofrece soporte nativo para conjuntos desde la versión 2019.
• Ada proporciona los Ada.Containers.Hashed_Setspaquetes Ada.Containers.Ordered_Sets.

Como se indicó en la sección anterior, en los lenguajes que no admiten directamente conjuntos pero sí matrices asociativas , los conjuntos se pueden emular utilizando matrices asociativas, usando los elementos como claves y un valor ficticio como valores, que se ignoran.

Una generalización del concepto de conjunto es el de multiconjunto o bolsa , similar a un conjunto pero que permite valores repetidos ("iguales") (duplicados). Esto se utiliza en dos sentidos distintos: los valores iguales se consideran idénticos y simplemente se cuentan, o bien 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 determinada. Alternativamente, se puede construir un multiconjunto de personas, donde dos personas se consideran equivalentes si tienen la misma edad (aunque pueden ser personas diferentes y tener nombres distintos), en cuyo caso cada par (nombre, edad) debe almacenarse, y al seleccionar una edad determinada se obtienen todas las personas de esa edad.

Formalmente, en informática, es posible que los objetos se consideren "iguales" bajo alguna relación de equivalencia , pero distintos bajo otra. Algunos tipos de implementaciones de multiconjuntos almacenan los objetos iguales distintos como elementos separados en la estructura de datos; mientras que otros la reducen a una sola versión (la primera encontrada) y mantienen un contador entero positivo que indica la multiplicidad del elemento.

Al igual que con los conjuntos, los multiconjuntos se pueden implementar de forma natural utilizando tablas hash o árboles, lo que da como resultado diferentes características de rendimiento.

El conjunto de todas las bolsas de 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 multiconjuntos ordenados y no ordenados. Proporciona la multisetclase para el multiconjunto ordenado, como una especie de contenedor asociativo , que implementa este multiconjunto utilizando un árbol de búsqueda binaria autoequilibrado . Proporciona la unordered_multisetclase para el multiconjunto no ordenado, como una especie de contenedor asociativo no ordenado , que implementa este multiconjunto utilizando una tabla hash . El multiconjunto no ordenado es estándar desde 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 de conjuntos múltiples:
  • 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 CFMutableBagcomo parte de CoreFoundation .
• La biblioteca estándar de Python incluye collections.Counter, 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 se dispone de una estructura de datos multiconjunto, una solución alternativa es utilizar un conjunto regular, pero sobrescribir el predicado de igualdad de sus elementos para que siempre devuelva "distinto de" en objetos distintos (sin embargo, esto seguirá sin poder 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 veces de lo que aparece 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 ₂ .

SELECCIONAR expresión1 , expresión2 ... DE nombre_tabla ...

MULTISET ( SELECCIONAR expresión1 , expresión2 ... DE nombre_tabla ...)

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