Generar todos los subconjuntos de un conjunto

Al determinar todos los subconjuntos de un conjunto determinado, el número de elementos (n) juega un papel crucial . Un algoritmo eficaz aprovecha técnicas recursivas para lograrlo.

Algoritmo recursivo

El algoritmo recursivo opera según el principio de que, para cada elemento, los subconjuntos se pueden dividir en dos categorías: las que contienen el elemento y las que lo excluyen. De lo contrario, estas dos particiones comparten subconjuntos idénticos.

A partir de n=1, tenemos dos subconjuntos: {} (el conjunto vacío) y {1}.

Para n>1, determinamos los subconjuntos de 1,...,n-1 y duplicarlos. A un conjunto se le agregará n a cada subconjunto, mientras que al otro permanecerá sin cambios. La unión de estos dos conjuntos produce el conjunto completo de subconjuntos.

Ejemplo ilustrativo

Generemos los subconjuntos de {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Toma {} , {1} y suma 2. Unión con {} , {1}: {{} , {1} , {2 } , {1, 2}}
• n=3: Sumar 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Sumar 4: {{} , {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4} , {1, 4} , {2, 4} , {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}}
• n=5: Sumar 5: {{} , {1} , {2} , {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4} , {3, 4} , {1, 3, 4} , {2, 3, 4} , {1, 2, 3, 4}, {5} , {1, 5}, {2, 5}, {1, 2, 5}, {3, 5}, {1, 3, 5}, {2, 3, 5}, {1, 2, 3, 5 }, {4, 5}, {1, 4, 5}, {2, 4, 5}, {1, 2, 4, 5}, {3, 4, 5} , {1, 3, 4, 5} , {2, 3, 4, 5} , {1, 2, 3, 4, 5}}

Así llegamos en los 32 subconjuntos de {1, 2, 3, 4, 5}.