Génération de tous les sous-ensembles d'un ensemble

Dans la détermination de tous les sous-ensembles d'un ensemble donné, le nombre d'éléments (n) joue un rôle crucial . Un algorithme efficace exploite des techniques récursives pour y parvenir.

Algorithme récursif

L'algorithme récursif fonctionne sur le principe selon lequel, pour chaque élément, les sous-ensembles peuvent être divisés en deux. catégories : celles contenant l’élément et celles l’excluant. Autrement, ces deux partitions partagent des sous-ensembles identiques.

En commençant par n=1, nous avons deux sous-ensembles : {} (l'ensemble vide) et {1}.

Pour n>1, nous déterminons les sous-ensembles de 1,...,n-1 et dupliquez-les. Un ensemble aura n ajouté à chaque sous-ensemble, tandis que l'autre restera inchangé. L'union de ces deux ensembles donne l'ensemble complet des sous-ensembles.

Exemple illustratif

Générons les sous-ensembles de {1, 2, 3, 4, 5} :

• n=1 : {{} , {1}}
• n=2 : Prenez {} , {1} et ajoutez 2. Union avec {} , {1} : {{} , {1} , {2 } , {1, 2}}
• n=3 : Ajouter 3 : {{} , {1} , {2} , {1, 2}, {3} , {1, 3} , {2, 3} , {1, 2, 3}}
• n=4 : Ajouter 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 : Ajoutez 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}}

On arrive donc au total 32 sous-ensembles de {1, 2, 3, 4, 5}.