Detaillierte Erläuterung der PHP-Permutationsrekursion sowie der Beispielcodes für Permutation und Kombination

1. Permutationsrekursion

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, stellt (i) Pi die Addition vor der Anordnung dar Pi Die Anordnung des Präfixes i, dann kann die vollständige Anordnung von n Elementen rekursiv definiert werden als:
① Wenn n=1, dann hat die Anordnung P nur ein Element i; i) Pi-Zusammensetzung; Aus der Definition geht hervor, dass, wenn die Anordnung Pi von (k-1) Elementen erzeugt wurde, die Anordnung von k Elementen durch Hinzufügen des Elements i vor jedem Pi erzeugt werden kann.

Code:

Nach vielen Testläufen stellte sich jedoch heraus, dass ein Problem vorliegt: Bei gleichen Elementen wiederholt sich die gesamte Anordnung.

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

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, ein Flag hinzugefügt, um Duplikate zu ermitteln, das Problem wurde gelöst (der Code lautet wie folgt):

2 Permutations- und Kombinationsbeispiele

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 vonDetaillierte Erläuterung der PHP-Permutationsrekursion sowie der Beispielcodes für Permutation und Kombination. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!