首页 > 代码库 > 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而生成。
1、
1 <?php 2 function rank($base, $temp=null) 3 { 4 $len = strlen($base); 5 if($len <= 1) 6 { 7 echo $temp.$base.‘<br/>‘; 8 } 9 else10 {11 for($i=0; $i< $len; ++$i)12 {13 rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);14 }15 }16 }17 rank(‘123‘);
不过，这样的算法有个问题：若是存在相同的元素，则全排列有重复。例如‘122‘的全排列只有三种情况：‘122‘、‘212‘、‘221‘；上面方法却有重复。
2、在上面算法的基础上价格判重操作即可
1 <?php 2 function fsRank($base, $temp=null) 3 { 4 static $ret = array(); 5 $len = strlen($base); 6 if($len <= 1) 7 { 8 //echo $temp.$base.‘<br/>‘; 9 $ret[] = $temp.$base;10 }11 else12 {13 for($i=0; $i< $len; ++$i)14 {15 $had_flag = false;16 for($j=0; $j<$i; ++$j)17 {18 if($base[$i] == $base[$j])19 {20 $had_flag = true;21 break;22 }23 }24 if($had_flag)25 {26 continue;27 }28 fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);29 }30 }31 return $ret;32 }33 print ‘<pre>‘;34 print_r(fsRank(‘122‘));35 print ‘</pre>‘;36 ?>
PHP实现全排列（递归算法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。