Comment trouver systématiquement tous les sous-ensembles d’un ensemble à l’aide d’un algorithme récursif ?

Trouver les sous-ensembles d'un ensemble

Déterminer tous les sous-ensembles d'un ensemble peut être une tâche difficile. Voici une approche qui utilise un algorithme récursif pour résoudre ce problème :

Pour un ensemble avec n éléments, nous pouvons considérer ses sous-ensembles en deux catégories : ceux qui incluent le nième élément et ceux qui n'en incluent pas.

Étape 1 : Cas de base

Si n vaut 1, les sous-ensembles sont simplement :

• {} (l'ensemble vide)
• {1}

Étape 2 : Cas récursif

Une fois que nous connaissons les sous-ensembles de l'ensemble {1, ..., n-1 }, nous pouvons construire les sous-ensembles pour l'ensemble {1, ..., n} comme suit :

• Faire deux copies des sous-ensembles pour {1, ..., n-1}.
• Pour une copie, ajoutez n à chaque sous-ensemble.
• Faites l'union des deux copies pour obtenir les sous-ensembles pour {1, ..., n}.

Exemple

Considérons l'ensemble {1, 2, 3, 4, 5}.

• Pour n = 1, les sous-ensembles sont {{} , {1}}.
• Pour n = 2, ajoutez 2 à chaque sous-ensemble de {}, {1} : {{2}, {1, 2}}. Prenez l'union : {{}, {1}, {2}, {1, 2}}.
• Répétez le processus pour n = 3, 4 et 5, en ajoutant chaque élément aux sous-ensembles du étape précédente.

Enfin, les sous-ensembles pour {1, 2, 3, 4, 5} sont : {{}, {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}}.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!