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

怪我咯
Libérer: 2023-03-13 17:56:01
original
1769 Les gens l'ont consulté

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;);
Copier après la connexion

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;
';
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal