Exemple de code d'algorithme récursif à permutation complète PHP

La

Récursivité est une technique de programmation importante. Cette méthode est utilisée pour laisser une fonction s’appeler de l’intérieur. Un exemple est le calcul de factorielles. La factorielle de 0 est spécifiquement définie comme 1. La factorielle d'un plus grand nombre se trouve en calculant 1 * 2 * ..., en augmentant de 1 à chaque fois, jusqu'à atteindre le nombre dont la factorielle doit être calculée.

Principe de l'algorithme
Si P représente l'arrangement complet de n éléments et Pi représente l'arrangement complet de n éléments qui n'inclut pas l'élément i, (i) Pi représente l'arrangement Si Pi est précédé du préfixe i, alors l'arrangement complet de n éléments peut être défini récursivement comme :
① Si n=1, alors l'arrangement P n'a qu'un seul élément i
② Si n>1, alors l'arrangement complet P est constitué de la permutation (i) Pi
D'après la définition, on voit que si la permutation Pi de (k-1) éléments a été générée, alors la permutation de k éléments peut être généré en ajoutant l'élément i devant chaque Pi .
Implémentation du code

Le code est le suivant :

function rank($base, $temp=null)
{
    $len = strlen($base);
    if($len <= 1)
    {
        echo $temp.$base.&#39;<br/>&#39;;
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
}
rank(&#39;123&#39;);

Cependant, après de nombreux tests et résultats d'exécution, il a été constaté qu'il y avait un problème : s'il y a les mêmes éléments, l’ensemble de l’arrangement sera répété.
Par exemple, il n'y a que trois situations pour l'arrangement complet de « 122 » : « 122 », « 212 » et « 221 » mais les méthodes ci-dessus sont répétées.
Légèrement modifié, ajout d'un drapeau pour identifier les doublons, résolu le problème (le code est le suivant) :

Le code est le suivant :

function fsRank($base, $temp=null)
{
    static $ret = array();
    $len = strlen($base);
    if($len <= 1)
    {
        //echo $temp.$base.&#39;<br/>&#39;;
        $ret[] = $temp.$base;
    }
    else
    {
        for($i=0; $i< $len; ++$i)
        {
            $had_flag = false;
            for($j=0; $j<$i; ++$j)
            {
                if($base[$i] == $base[$j])
                {
                    $had_flag = true;
                    break;
                }
            }
            if($had_flag)
            {
                continue;
            }
            fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
    return $ret;
}
print &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r(fsRank(&#39;122&#39;));
print &#39;

';

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!