- 相關(guān)推薦
解讀php全排列遞歸算法代碼
php全排列遞歸算法代碼，需要的朋友可以參考下，就跟隨百分網(wǎng)小編一起去了解下吧，想了解更多相關(guān)信息請持續(xù)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
算法原理
如果用P表示n個元素的全排列，而Pi表示n個元素中不包含元素i的全排列，(i)Pi表示在排列Pi前面加上前綴i的排列，那么n個元素的全排列可遞歸定義為：
① 如果n=1，則排列P只有一個元素i；
② 如果n>1，則全排列P由排列(i)Pi構(gòu)成；
根據(jù)定義，可以看出如果已經(jīng)生成（k-1）個元素的排列Pi，那么k個元素的排列可以在每個Pi前面加上元素i而生成。
代碼實現(xiàn)
復(fù)制代碼 代碼如下:
function rank($base, $temp=null)
{
$len = strlen($base);
if($len <= 1)
{
echo $temp.$base.'<br/>';
}
else
{
for($i=0; $i< $len; ++$i)
{
rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
}
}
}
rank('123');
不過，經(jīng)多次測試運行結(jié)果，發(fā)現(xiàn)存在一個問題：若是存在相同的元素，則全排列有重復(fù)。
例如'122'的全排列只有三種情況：'122'、'212'、'221'；上面方法卻有重復(fù)。
略修改，加個判斷重復(fù)的標志，解決了問題（代碼如下）：
復(fù)制代碼 代碼如下:
function fsRank($base, $temp=null)
{
static $ret = array();
$len = strlen($base);
if($len <= 1)
{
//echo $temp.$base.'<br/>';
$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 '<pre>';
print_r(fsRank('122'));
print '</pre>';
【解讀php全排列遞歸算法代碼】相關(guān)文章：
PHP遞歸效率分析08-25
java中全排列是如何生成算法09-05
PHP中獎概率的抽獎算法程序代碼實例08-05
PHP經(jīng)典算法題09-05
C語言中遞歸算法的剖析08-15
php經(jīng)典算法介紹10-05
PHP紅包算法11-04
php遞歸遍歷多維數(shù)組的方法10-06