PHP の完全に配置された再帰アルゴリズム コード

アルゴリズム原理

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

コードをコピー コードは次のとおりです。

function Rank($base, $temp=null) )
{
$len = strlen($base);
if($len {
echo $temp.$base.'
';
}
else
{
for($i=0; $i< $len; $i)
{
ランク(substr($base, 0, $ i) substr($base, $i 1, $len-$i-1), $temp.$base[$i]);
;


ただし、複数のテストの後実行すると、同じ要素がある場合、配置全体が繰り返されるという問題があることが判明しました。
たとえば、「122」の完全な配置には「122」、「212」、「221」の 3 つの状況しかありませんが、上記の方法が繰り返されます。

少し変更し、重複を識別するためのフラグを追加し、問題を解決しました (コードは次のとおりです):



コードをコピーします

コードは次のとおりです: function fsRank($base, $temp=null)

{

static $ret = array();
$len = strlen($base);
if($len < = 1)
{
//echo $temp.$base.'
';
$ret[] = $temp.$base;
}
else
{
for($i=0; $i< $len; $i)
{
$had_flag = false;
for($j= 0; $ j＆lt; $ j）
} <：rank（$ base、0、$ i）。 -1), $temp.$base[$i]);
}
}
return $ret;
}
print '

';<BR>print_r( fsRank('122'));<BR>print '

';