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.'<br/>'; } else { for($i=0; $i< $len; ++$i) { rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]); } } } rank('123');
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.'<br/>'; $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 '<pre class="brush:php;toolbar:false">'; print_r(fsRank('122')); print '';
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!