Comment puis-je générer toutes les combinaisons d'un ensemble donné en PHP à l'aide d'un algorithme récursif ?

Générer toutes les combinaisons à l'aide d'un algorithme en PHP

L'une des tâches fondamentales en informatique consiste à générer des combinaisons à partir d'un ensemble donné. Dans ce contexte, une combinaison fait référence à un sous-ensemble d'éléments de l'ensemble d'origine, avec une taille spécifiée.

Par exemple, considérons un ensemble A = {A, B, C}. Voici comment obtenir des combinaisons de différentes tailles :

Générer des combinaisons à l'aide d'un algorithme récursif

Pour résoudre ce problème, nous pouvons utiliser un algorithme récursif qui explore toutes les combinaisons possibles. . Voici une explication étape par étape :

1. Initialisez un tableau vide $combinations pour stocker les combinaisons.
2. Si $size est égal à 1, nous avons atteint le cas de base et peut renvoyer $combinations.
3. Parcourir les $chars et le courant $combinations.
4. Pour chaque combinaison et caractère, ajoutez le caractère à la combinaison et ajoutez la nouvelle combinaison à $new_combinations.
5. Appelez récursivement la fonction d'échantillonnage avec $new_combinations mis à jour et décrémentez $size de 1.

Mise en œuvre dans PHP

function sampling($chars, $size, $combinations = []) {
    if (empty($combinations)) {
        $combinations = $chars;
    }
    if ($size == 1) {
        return $combinations;
    }
    $new_combinations = [];
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }
    return sampling($chars, $size - 1, $new_combinations);
}

Exemple

Considérons notre ensemble original A = {A, B, C}.

$chars = ['A', 'B', 'C'];
$output = sampling($chars, 2);
var_dump($output);

Sortie

array(9) {
  [0]=>
  string(2) "AA"
  [1]=>
  string(2) "AB"
  [2]=>
  string(2) "AC"
  [3]=>
  string(2) "BA"
  [4]=>
  string(2) "BB"
  [5]=>
  string(2) "BC"
  [6]=>
  string(2) "CA"
  [7]=>
  string(2) "CB"
  [8]=>
  string(2) "CC"
}

Cet algorithme fournit une approche systématique pour générer tous combinaisons d’une taille spécifique à partir d’un ensemble donné. Sa nature récursive permet une exploration efficace de toutes les combinaisons possibles, quelle que soit la taille de l'ensemble d'entrée.

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!