El conjunto potencia reúne todos los subconjuntos posibles de un conjunto. Si un conjunto tiene n elementos, entonces tiene 2ⁿ subconjuntos.
En el tema anterior vimos que un conjunto puede estar contenido dentro de otro. Ahora estudiaremos todos los subconjuntos que pueden formarse a partir de un conjunto dado.
El conjunto que contiene todos esos subconjuntos se llama conjunto potencia. Este concepto aparece en combinatoria, análisis de posibilidades, permisos, selección de opciones y generación de casos de prueba.
El conjunto potencia de un conjunto A es el conjunto formado por todos los subconjuntos de A. Se representa como P(A) o como 𝒫(A).
Observa que el conjunto potencia contiene conjuntos como elementos.
El conjunto vacío es subconjunto de cualquier conjunto. Por eso, siempre forma parte del conjunto potencia.
Aunque A tenga muchos elementos, su conjunto potencia siempre incluye ∅.
Todo conjunto es subconjunto de sí mismo. Por lo tanto, el conjunto original también forma parte de su conjunto potencia.
El conjunto potencia contiene desde el subconjunto vacío hasta el conjunto completo.
Si un conjunto tiene un solo elemento, su conjunto potencia tiene dos subconjuntos: el vacío y el conjunto completo.
En este caso, |A| = 1 y |P(A)| = 2.
Con dos elementos se obtienen cuatro subconjuntos.
En este caso, |A| = 2 y |P(A)| = 4.
Con tres elementos se obtienen ocho subconjuntos.
En este caso, |A| = 3 y |P(A)| = 8.
Si un conjunto tiene n elementos, cada elemento tiene dos posibilidades: estar o no estar en un subconjunto. Por eso, la cantidad total de subconjuntos es 2ⁿ.
Esta fórmula permite calcular la cantidad de subconjuntos sin tener que listarlos uno por uno.
| Cardinalidad de A | Cantidad de subconjuntos | Cálculo |
|---|---|---|
| |A| = 0 | 1 | 2⁰ = 1 |
| |A| = 1 | 2 | 2¹ = 2 |
| |A| = 2 | 4 | 2² = 4 |
| |A| = 3 | 8 | 2³ = 8 |
| |A| = 4 | 16 | 2⁴ = 16 |
| |A| = 5 | 32 | 2⁵ = 32 |
El conjunto vacío tiene un solo subconjunto: él mismo. Por eso, su conjunto potencia contiene un elemento.
Esto coincide con la fórmula 2⁰ = 1.
El conjunto potencia contiene todos los subconjuntos, incluyendo el conjunto original. Si queremos contar solo los subconjuntos propios, debemos excluir el conjunto completo.
Por ejemplo, si A = {a, b, c}, entonces tiene 8 subconjuntos y 7 subconjuntos propios.
Podemos generar todos los subconjuntos de un arreglo agregando cada elemento a los subconjuntos ya construidos.
function conjuntoPotencia(elementos) {
return elementos.reduce(
(subconjuntos, elemento) => [
...subconjuntos,
...subconjuntos.map(subconjunto => [...subconjunto, elemento])
],
[[]]
);
}
const resultado = conjuntoPotencia(["a", "b", "c"]);
console.log(resultado);
console.log(resultado.length);El arreglo vacío [] representa al conjunto vacío. Para tres elementos, el resultado tiene ocho subconjuntos.
El conjunto potencia sirve para representar todas las formas posibles de elegir opciones. Por ejemplo, si una interfaz permite activar tres filtros, cada subconjunto representa una combinación de filtros activos.
function conjuntoPotencia(elementos) {
return elementos.reduce(
(subconjuntos, elemento) => [
...subconjuntos,
...subconjuntos.map(subconjunto => [...subconjunto, elemento])
],
[[]]
);
}
const filtros = ["precio", "categoria", "stock"];
const combinaciones = conjuntoPotencia(filtros);
console.log(combinaciones);La salida contiene desde la combinación sin filtros hasta la combinación con todos los filtros activos.
La cantidad de subconjuntos crece muy rápido. Cada nuevo elemento duplica la cantidad de subconjuntos posibles.
| Elementos | Subconjuntos | Observación |
|---|---|---|
| 10 | 1.024 | Aún manejable en muchos casos |
| 20 | 1.048.576 | Ya puede ser costoso |
| 30 | 1.073.741.824 | Puede ser impracticable generar todo |
En programación, esta explosión combinatoria obliga a pensar con cuidado antes de generar todos los subconjuntos de una colección grande.
| Área | Uso del conjunto potencia | Ejemplo |
|---|---|---|
| Pruebas de software | Generar combinaciones de opciones | Probar filtros activos e inactivos |
| Permisos | Enumerar combinaciones de accesos | Leer, editar, publicar |
| Optimización | Explorar subconjuntos candidatos | Seleccionar características o recursos |
| Interfaces | Combinar estados posibles | Opciones seleccionadas por el usuario |
El conjunto potencia permite estudiar todas las combinaciones posibles de elementos dentro de un conjunto. Es una idea simple, pero muy poderosa, especialmente cuando se trabaja con opciones, permisos, filtros o casos de prueba.
En el próximo tema estudiaremos la unión de conjuntos.