Beispielcode für einen rekursiven PHP-Algorithmus mit vollständiger Permutation

Rekursion ist eine wichtige Programmiertechnik. Diese Methode wird verwendet, um eine Funktion von innen heraus aufrufen zu lassen. Ein Beispiel ist die Berechnung von Fakultäten. Die Fakultät von 0 wird speziell als 1 definiert. Die Fakultät einer größeren Zahl wird ermittelt, indem man 1 * 2 * ... berechnet und dabei jedes Mal um 1 erhöht, bis die Zahl erreicht ist, deren Fakultät berechnet werden soll.

Algorithmusprinzip
Wenn P die vollständige Anordnung von n Elementen darstellt und Pi die vollständige Anordnung von n Elementen darstellt, die das Element i nicht enthält, (i) stellt Pi die Anordnung dar Für eine Anordnung mit dem Präfix i vor Pi kann die vollständige Anordnung von n Elementen rekursiv definiert werden als:
① Wenn n=1, dann hat die Anordnung P nur ein Element i;
② Wenn n> 1, dann besteht die vollständige Anordnung P aus der Permutation (i) Pi
Gemäß der Definition ist ersichtlich, dass, wenn die Permutation Pi von (k-1) Elementen erzeugt wurde, dann die Permutation von k Elementen kann durch Hinzufügen des Elements i vor jedem Pi generiert werden.
Code-Implementierung

Der Code lautet wie folgt:

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;);

Nach mehrmaligem Testen der Laufergebnisse wurde jedoch festgestellt, dass ein Problem vorliegt: Wenn vorhanden Sind die Elemente die gleichen, wiederholt sich die gesamte Anordnung.
Zum Beispiel gibt es nur drei Situationen für die vollständige Anordnung von „122“: „122“, „212“ und „221“, aber die oben genannten Methoden werden wiederholt.
Leicht geändert, eine Markierung hinzugefügt, um Duplikate zu identifizieren, das Problem gelöst (der Code lautet wie folgt):

Der Code lautet wie folgt:

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;

';

Das obige ist der detaillierte Inhalt vonBeispielcode für einen rekursiven PHP-Algorithmus mit vollständiger Permutation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!