Explication détaillée de la récursion de permutation PHP et des exemples de codes de permutation et de combinaison

1. Récursion de permutation

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'ajout devant l'arrangement Pi L'arrangement 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 ; i) Composition Pi
Selon ; Dans la définition, on peut voir que si l'arrangement Pi de (k-1) éléments a été généré, alors l'arrangement de k éléments peut être généré en ajoutant l'élément i devant chaque Pi.

Code :

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, 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 indicateur pour déterminer la duplication, résolution du problème (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;

';2. Exemples de permutation et de combinaison

.

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!