Comment générer toutes les permutations de chaînes à l'aide du backtracking en PHP ?

Permutations d'une chaîne à l'aide d'une approche de retour en arrière

La permutation fait référence à la réorganisation des caractères d'une chaîne dans tous les ordres possibles. Pour générer toutes les permutations d'une chaîne en PHP, nous pouvons utiliser un algorithme de retour en arrière.

Supposons que nous ayons une chaîne "hé".

1. Diviser la chaîne en caractères individuels :

   Nous commençons par diviser la chaîne en un tableau de caractères individuels. Dans ce cas, ['h', 'e', ​​'y'].

2. Générer des permutations de manière récursive :

   En utilisant la récursivité, nous générer des permutations en échangeant systématiquement les caractères et en générant tous les possibles combinaisons.

3. Retour en arrière pour restaurer l'ordre d'origine :

   Après avoir généré une permutation, nous revenons en arrière pour restaurer l'ordre d'origine des personnages. Cela empêche la génération de permutations en double.

Exemple de code :

// Function to generate and print all permutations of $str (N = strlen($str)).
function permute($str, $i, $n) {
    if ($i == $n) {
        print "$str\n";
    } else {
        for ($j = $i; $j < $n; $j++) {
            swap($str, $i, $j);
            permute($str, $i + 1, $n);
            swap($str, $i, $j); // Backtrack.
        }
    }
}

// Function to swap the characters at positions $i and $j of $str.
function swap(&$str, $i, $j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}

$str = "hey";
permute($str, 0, strlen($str)); // Call the function.

Sortie :

hey
hye
ehy
eyh
yeh
yhe

Cette approche de retour en arrière garantit que toutes les permutations sont systématiquement générées et imprimées.

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!