PHP 完全置換再帰アルゴリズムのサンプルコード-PHPチュートリアル-php.cn

PHP 完全置換再帰アルゴリズムのサンプルコード

怪我咯

リリース： 2023-03-13 17:56:01

オリジナル

1785 人が閲覧しました

再帰は重要なプログラミングテクニックです。このメソッドは、関数が内部からそれ自体を呼び出すために使用されます。一例は階乗の計算です。 0 の階乗は 1 として明確に定義されています。より大きな数値の階乗は、階乗を計算する数値に達するまで、1 * 2 * ... を計算するたびに 1 ずつ増加して求められます。

アルゴリズム原理
P が n 個の要素の完全な配置を表し、Pi が要素 i を含まない n 個の要素の完全な配置を表す場合、 (i) Pi は、配置 Pi の前に接頭語 i を付けた配置を表します、 n 個の要素の合計配置は次のように再帰的に定義できます。
① n=1 の場合、配置 P には要素 i が 1 つだけあります。
② n>1 の場合、全体の配置 P は配置 (i)Pi で構成されます。 ;
定義によれば、(k-1) 個の要素の順列 Pi が生成されている場合、各 Pi の前に要素 i を追加することで k 要素の順列を生成できることがわかります。
コードの実装

コードは次のとおりです:

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

ログイン後にコピー

しかし、何度もテストを実行した結果、同じ要素がある場合、配置全体が繰り返されるという問題があることがわかりました。
たとえば、「122」の完全な配置には「122」、「212」、「221」の 3 つの状況しかありませんが、上記の方法が繰り返されます。
わずかに変更され、重複を識別するためのフラグが追加され、問題が解決されました (コードは次のとおりです):

コードは次のとおりです:

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;

ログイン後にコピー

以上がPHP 完全置換再帰アルゴリズムのサンプルコードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。