php递归算法 解读php全排列递归算法代码

　　php全排列递归算法代码，需要的朋友可以参考下，就跟随百分网小编一起去了解下吧，想了解更多相关信息请持续关注我们应届毕业生考试网!

　　算法原理

　　如果用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.'
';

　　}

　　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.'
';

　　$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 '

';
　　print_r(fsRank('122'));
　　print '