php全排列遞歸算法代碼
更新時間:2012年10月09日 19:40:45 作者:
php全排列遞歸算法代碼,需要的朋友可以參考下
算法原理
如果用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)
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ù)的標(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個元素的全排列,而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ù)的標(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ù)三種實現(xiàn)方法及如何實現(xiàn)數(shù)字累加
- PHP 無限分類三種方式 非函數(shù)的遞歸調(diào)用!
- php菜單/評論數(shù)據(jù)遞歸分級算法的實現(xiàn)方法
- PHP遞歸算法的簡單實例
- PHP基于遞歸算法解決兔子生兔子問題
- PHP基于非遞歸算法實現(xiàn)先序、中序及后序遍歷二叉樹操作示例
- PHP基于二分法實現(xiàn)數(shù)組查找功能示例【循環(huán)與遞歸算法】
- PHP實現(xiàn)字符串翻轉(zhuǎn)功能的方法【遞歸與循環(huán)算法】
- PHP基于遞歸實現(xiàn)的約瑟夫環(huán)算法示例
- PHP使用遞歸算法無限遍歷數(shù)組示例
- php獲得文件夾下所有文件的遞歸算法的簡單實例
- PHP二分查找算法示例【遞歸與非遞歸方法】
- PHP冒泡算法詳解(遞歸實現(xiàn))
- 關(guān)于PHP遞歸算法和應(yīng)用方法介紹
- PHP遞歸算法的詳細(xì)示例分析
- php實現(xiàn)遞歸的三種基本方式
相關(guān)文章
php array_flip() 刪除數(shù)組重復(fù)元素
在PHP中,用于刪除數(shù)組中重復(fù)元素有一個可用的函數(shù),那就是 array_unique(), 但是它并不是一個最高效的方法,使用array_flip() 函數(shù)將比array_uniqure()在速度上高出五倍左右。2009-01-01PHP實現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問題示例
這篇文章主要介紹了PHP實現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問題,結(jié)合具體實例形式分析了php使用單鏈表解決約瑟夫環(huán)問題的算法原理與相關(guān)操作技巧,需要的朋友可以參考下2017-09-09Sorting Array Values in PHP(數(shù)組排序)
有時候,你可能需要對數(shù)組內(nèi)的值進(jìn)行排序,那么就可以參考下面的文章。2011-09-09