php全排列递归算法示例代码
程序员文章站
2022-06-02 09:50:01
...
递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的,每次增加 1,直至达到要计算其阶乘的那个数。
算法原理
如果用P表示n个元素的全排列,而Pi表示n个元素中不包含元素i的全排列,(i)Pi表示在排列Pi前面加上前缀i的排列,那么n个元素的全排列可递归定义为:
① 如果n=1,则排列P只有一个元素i;
② 如果n>1,则全排列P由排列(i)Pi构成;
根据定义,可以看出如果已经生成(k-1)个元素的排列Pi,那么k个元素的排列可以在每个Pi前面加上元素i而生成。
代码实现
代码如下:
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');
不过,经多次测试运行结果,发现存在一个问题:若是存在相同的元素,则全排列有重复。
例如'122'的全排列只有三种情况:'122'、'212'、'221';上面方法却有重复。
略修改,加个判断重复的标志,解决了问题(代码如下):
代码如下:
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全排列递归算法示例代码的详细内容,更多请关注其它相关文章!