Comment puis-je générer toutes les permutations possibles d'un tableau de chaînes en PHP en utilisant à la fois des approches récursives et itératives ?

Génération de permutations de tableau en PHP

Étant donné un tableau de chaînes, telles que ['peter', 'paul', 'mary'] , la tâche est de trouver toutes les permutations possibles de ses éléments. Les permutations impliquent de réorganiser les éléments de manière à préserver leur identité. Le résultat souhaité serait :

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter

Solution 1 : Utiliser une fonction récursive

Une fonction récursive peut être utilisée pour générer des permutations en sélectionnant et désélectionnant chaque élément du tableau. La fonction pc_permute ci-dessous explore toutes les combinaisons possibles :

function pc_permute($items, $perms = array()) {
    if (empty($items)) { 
        echo join(' ', $perms) . "<br />";
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

Cette fonction prend deux paramètres : $items (le tableau d'entrée) et $perms (un paramètre facultatif pour garder une trace de la permutation actuelle). Il parcourt les éléments de $items, en supprime un, l'ajoute au début de $perms, puis s'appelle de manière récursive avec les arguments modifiés. Lorsque le tableau d'entrée devient vide, la fonction imprime la permutation actuelle.

Solution 2 : Utiliser une fonction itérative

Alternativement, une approche itérative peut être utilisée pour générer des permutations. La fonction pc_next_permutation effectue les étapes suivantes :

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

Cette fonction prend deux paramètres : $p (le tableau d'entrée) et $size (la longueur du tableau d'entrée). Il parcourt le tableau dans l’ordre inverse, à la recherche d’une valeur inférieure à l’élément suivant. Si aucune valeur de ce type n’est trouvée, cela signifie que la permutation actuelle est la dernière. Sinon, il échange la valeur avec la valeur suivante plus grande, puis inverse les éléments restants dans la permutation.

En appelant pc_next_permutation de manière itérative sur un tableau trié, toutes les permutations possibles peuvent être générées. Le code suivant illustre cette approche :

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

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!