Heim  >  Artikel  >  Backend-Entwicklung  >  Detaillierte Erläuterung der PHP-Permutationsrekursion sowie der Beispielcodes für Permutation und Kombination

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

伊谢尔伦
伊谢尔伦Original
2017-07-17 11:02:282131Durchsuche

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!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn