Comment générer tous les sous-ensembles d'un ensemble à l'aide d'un algorithme récursif ?

Rechercher tous les sous-ensembles d'un ensemble à l'aide d'un algorithme récursif

Étant donné un ensemble avec n éléments, trouver tous les sous-ensembles possibles est une tâche courante. Cet article présente une explication étape par étape d'un algorithme récursif efficace pour y parvenir.

Approche récursive

L'algorithme est basé sur l'idée que pour chaque élément dans un ensemble, il y a deux possibilités :

1. Inclure l'élément : Cela crée un nouveau sous-ensemble qui inclut l'élément.
2. Exclure l'élément : Cela crée un nouveau sous-ensemble qui exclut l'élément.

En considérant les deux possibilités pour chaque élément, nous couvrons tous combinaisons possibles et donc trouver tous les sous-ensembles.

Pas à pas Explication

Prenons l'ensemble {1, 2, 3, 4, 5} comme exemple.

1. Cas de base : Pour n= 1, l'ensemble a un seul élément (par exemple, {1}). Les sous-ensembles sont {{}} (l'ensemble vide) et {{1}} (contenant seulement 1).

2. Cas récursif : Pour n>1, nous pouvons casser le problème se décompose en deux sous-problèmes :

   • Trouver des sous-ensembles de {1, 2, 3, 4, 5-1} :Nous appelons récursivement l'algorithme pour les n-1 premiers éléments et obtenons un ensemble de sous-ensembles.
   • Faire deux copies de l'ensemble de sous-ensembles : Une copie sert à inclure l'élément n dans chaque sous-ensemble et l'autre à l'exclure.
   • Ajoutez n aux sous-ensembles dans la copie d'inclusion : Par exemple, si nous avons {{}, {1}, {2}}, ajouter 5 donnerait {{}, {1}, {2}, {5}, {1, 5 }, {2, 5}}.
   • Prenons l'union des deux copies : Cela nous donne l'ensemble complet de sous-ensembles.

Exemple

Calculons les sous-ensembles de {1, 2, 3, 4, 5} de manière récursive :

• Étape 1 (n=1) : Sous-ensembles = {{}, {1}}
• Étape 2 (n=2) : Sous-ensembles = {{}, {1}, { 2}, {1, 2}} (faire une copie pour {2})
• Étape 3 (n=3) : Sous-ensembles = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}} (ajoutez 3 au { 2} copie)
• Étape 4 (n=4) : Sous-ensembles = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}} (ajouter 4 à la copie {3})
• Étape 5 (n=5) : Sous-ensembles = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4} , {5}, {1, 5}, {2, 5}, {1, 2, 5}} (ajoutez 5 au {4} copie)

Par conséquent, l'ensemble complet des sous-ensembles est {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}, {4}, {1, 4}, {2, 4}, {1, 2, 4}, {5}, {1, 5}, {2, 5}, {1, 2, 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!