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 { echo $temp.$base.''; } else { for($i=0; $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 { //echo $temp.$base.''; $ret[] = $temp.$base; } else { for($i=0; $i { $had_flag = false; for($j=0; $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 '登录后复制';