Gerando todos os subconjuntos de um conjunto

Na determinação de todos os subconjuntos de um determinado conjunto, o número de elementos (n) desempenha um papel crucial . Um algoritmo eficaz aproveita técnicas recursivas para conseguir isso.

Algoritmo Recursivo

O algoritmo recursivo opera no princípio de que, para cada elemento, os subconjuntos podem ser particionados em dois categorias: aquelas que contêm o elemento e aquelas que o excluem. Caso contrário, essas duas partições compartilham subconjuntos idênticos.

Começando com n=1, temos dois subconjuntos: {} (o conjunto vazio) e {1}.

Para n>1, determinamos os subconjuntos de 1,...,n-1 e duplicá-los. Um conjunto terá n adicionado a cada subconjunto, enquanto o outro permanecerá inalterado. A união desses dois conjuntos produz o conjunto completo de subconjuntos.

Exemplo ilustrativo

Vamos gerar os subconjuntos de {1, 2, 3, 4, 5}:

• n=1: {{} , {1}}
• n=2: Pegue {} , {1} e adicione 2. União com {} , {1}: {{} , {1} , {2} , {1, 2}}
• n=3: Adicione 3: {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4: Adicione 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: Adicione 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}}

Assim, chegamos a todos os 32 subconjuntos de {1, 2, 3, 4, 5}.