php全排列遞歸算法代碼
更新時(shí)間：2012年10月09日 19:40:45 作者：
php全排列遞歸算法代碼，需要的朋友可以參考下
算法原理
如果用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)
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)多次測(cè)試運(yùn)行結(jié)果，發(fā)現(xiàn)存在一個(gè)問題：若是存在相同的元素，則全排列有重復(fù)。
例如'122'的全排列只有三種情況：'122'、'212'、'221'；上面方法卻有重復(fù)。
略修改，加個(gè)判斷重復(fù)的標(biāo)志，解決了問題（代碼如下）：
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>';
如果用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');
不過，經(jīng)多次測(cè)試運(yùn)行結(jié)果，發(fā)現(xiàn)存在一個(gè)問題：若是存在相同的元素，則全排列有重復(fù)。
例如'122'的全排列只有三種情況：'122'、'212'、'221'；上面方法卻有重復(fù)。
略修改，加個(gè)判斷重復(fù)的標(biāo)志，解決了問題（代碼如下）：
復(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遞歸的三種常用方式
- php遞歸函數(shù)三種實(shí)現(xiàn)方法及如何實(shí)現(xiàn)數(shù)字累加
- PHP 無限分類三種方式 非函數(shù)的遞歸調(diào)用！
- php菜單/評(píng)論數(shù)據(jù)遞歸分級(jí)算法的實(shí)現(xiàn)方法
- PHP遞歸算法的簡(jiǎn)單實(shí)例
- PHP基于遞歸算法解決兔子生兔子問題
- PHP基于非遞歸算法實(shí)現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP基于二分法實(shí)現(xiàn)數(shù)組查找功能示例【循環(huán)與遞歸算法】
- PHP實(shí)現(xiàn)字符串翻轉(zhuǎn)功能的方法【遞歸與循環(huán)算法】
- PHP基于遞歸實(shí)現(xiàn)的約瑟夫環(huán)算法示例
- PHP使用遞歸算法無限遍歷數(shù)組示例
- php獲得文件夾下所有文件的遞歸算法的簡(jiǎn)單實(shí)例
- PHP二分查找算法示例【遞歸與非遞歸方法】
- PHP冒泡算法詳解（遞歸實(shí)現(xiàn)）
- 關(guān)于PHP遞歸算法和應(yīng)用方法介紹
- PHP遞歸算法的詳細(xì)示例分析
- php實(shí)現(xiàn)遞歸的三種基本方式
相關(guān)文章
這篇文章主要介紹了php簡(jiǎn)單隨機(jī)字符串生成方法,結(jié)合實(shí)例形式分析了php生成隨機(jī)字符串的相關(guān)技巧與注意事項(xiàng),需要的朋友可以參考下2017-04-04
這篇文章主要介紹了PHP附件下載中文名稱亂碼的解決方法,分析了中文亂碼形成的原因及對(duì)應(yīng)的編碼轉(zhuǎn)換方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了php建立Ftp連接的方法,實(shí)例分析了php操作FTP的相關(guān)函數(shù)及使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-03-03
MYSQL的優(yōu)化是非常重要的。其他最常用也最需要優(yōu)化的就是limit。mysql的limit給分頁(yè)帶來了極大的方便，但數(shù)據(jù)量一大的時(shí)候，limit的性能就急劇下降。2008-01-01
php token使用與驗(yàn)證示例【測(cè)試可用】
這篇文章主要介紹了php token使用與驗(yàn)證方法,通過對(duì)form表單hidden提交字段的處理實(shí)現(xiàn)token驗(yàn)證功能,防止非法來源數(shù)據(jù)的訪問,需要的朋友可以參考下2017-08-08
這篇文章主要介紹了PHP獲取表單所有復(fù)選框的值的方法,是進(jìn)行PHP程序設(shè)計(jì)表單操作中所必須掌握的常用技巧,需要的朋友可以參考下2014-08-08
php數(shù)據(jù)結(jié)構(gòu)之順序鏈表與鏈?zhǔn)骄€性表示例
這篇文章主要介紹了php數(shù)據(jù)結(jié)構(gòu)之順序鏈表與鏈?zhǔn)骄€性表,結(jié)合實(shí)例形式較為詳細(xì)的分析了php實(shí)現(xiàn)順序鏈表與鏈?zhǔn)骄€性表的各種常用操作技巧,需要的朋友可以參考下2018-01-01
php將圖片保存入mysql數(shù)據(jù)庫(kù)失敗的解決方法
這篇文章主要介紹了php將圖片保存入mysql數(shù)據(jù)庫(kù)失敗的解決方法,詳細(xì)分析了php將圖片保存入數(shù)據(jù)庫(kù)遇到的問題及對(duì)應(yīng)的解決方法,并總結(jié)了相關(guān)的技巧,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-12-12
php實(shí)現(xiàn)簡(jiǎn)單的MVC框架實(shí)例
這篇文章主要介紹了php實(shí)現(xiàn)簡(jiǎn)單的MVC框架,較為詳細(xì)的分析了php實(shí)現(xiàn)MVC框架的相關(guān)實(shí)現(xiàn)技巧與注意事項(xiàng),具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-09-09
PHP通過GD庫(kù)實(shí)現(xiàn)驗(yàn)證碼功能示例
這篇文章主要介紹了PHP通過GD庫(kù)實(shí)現(xiàn)驗(yàn)證碼功能,結(jié)合實(shí)例形式分析了php驗(yàn)證碼相關(guān)圖片繪制、輸出操作實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-02-02