php全排列递归算法代码
发布时间：2020-12-13 06:11:23 所属栏目：PHP教程 来源：网络整理
导读：算法原理 如果用P表示n个元素的全排列，而Pi表示n个元素中不包含元素i的全排列，(i)Pi表示在排列Pi前面加上前缀i的排列，那么n个元素的全排列可递归定义为： ① 如果n=1，则排列P只有一个元素i； ② 如果n>1，则全排列P由排列(i)Pi构成； 根据定义，可以看出
算法原理如果用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,$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,$temp.$base[$i]); } } return $ret; } print ' ';'; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |