解讀php全排列遞歸算法代碼

　　php全排列遞歸算法代碼，需要的朋友可以參考下，就跟隨百分網(wǎng)小編一起去了解下吧，想了解更多相關(guān)信息請(qǐng)持續(xù)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!

　　算法原理

　　如果用P表示n個(gè)元素的全排列，而Pi表示n個(gè)元素中不包含元素i的全排列，(i)Pi表示在排列Pi前面加上前綴i的排列，那么n個(gè)元素的全排列可遞歸定義為：

　�、� 如果n=1，則排列P只有一個(gè)元素i；

　�、� 如果n>1，則全排列P由排列(i)Pi構(gòu)成；

　　根據(jù)定義，可以看出如果已經(jīng)生成（k-1）個(gè)元素的排列Pi，那么k個(gè)元素的排列可以在每個(gè)Pi前面加上元素i而生成。

　　代碼實(shí)現(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');

　　不過(guò)，經(jīng)多次測(cè)試運(yùn)行結(jié)果，發(fā)現(xiàn)存在一個(gè)問(wèn)題：若是存在相同的元素，則全排列有重復(fù)。

　　例如'122'的全排列只有三種情況：'122'、'212'、'221'；上面方法卻有重復(fù)。

　　略修改，加個(gè)判斷重復(fù)的標(biāo)志，解決了問(wèn)題（代碼如下）：

　　復(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使用遞歸算法無(wú)限遍歷數(shù)組示例05-20

php遞歸創(chuàng)建和刪除文件夾的代碼01-20

java中全排列是如何生成算法05-18

PHP遞歸效率分析03-09

PHP中獎(jiǎng)概率的抽獎(jiǎng)算法程序代碼實(shí)例08-05

C語(yǔ)言中遞歸算法的剖析08-15

php經(jīng)典算法介紹02-26

PHP經(jīng)典算法題03-19

PHP紅包算法04-06