算法原理@H_403_1@
@H_403_1@如果用P表示n个元素的全排列，而Pi表示n个元素中不包含元素i的全排列，(i)Pi表示在排列Pi前面加上前缀i的排列，那么n个元素的全排列可递归定义为：@H_403_1@ ① 如果n=1，则排列P只有一个元素i；@H_403_1@ ② 如果n>1，则全排列P由排列(i)Pi构成；@H_403_1@根据定义，可以看出如果已经生成（k-1）个元素的排列Pi，那么k个元素的排列可以在每个Pi前面加上元素i而生成。@H_403_1@代码实现@H_403_1@ 代码如下:
403_1@function rank($base,$temp=null)@H_403_1@{@H_403_1@ $len = strlen($base);@H_403_1@ if($len <= 1)@H_403_1@ {@H_403_1@ echo $temp.$base.'
';@H_403_1@ }@H_403_1@ else@H_403_1@ {@H_403_1@ for($i=0; $i< $len; ++$i)@H_403_1@ {@H_403_1@ rank(substr($base,$i).substr($base,$i+1,$len-$i-1),$temp.$base[$i]);@H_403_1@ }@H_403_1@ }@H_403_1@}@H_403_1@rank('123');@H_403_1@
@H_403_1@不过，经多次测试运行结果，发现存在一个问题：若是存在相同的元素，则全排列有重复。@H_403_1@例如'122'的全排列只有三种情况：'122'、'212'、'221'；上面方法却有重复。@H_403_1@略修改，加个判断重复的标志，解决了问题（代码如下）：@H_403_1@';@H_403_1@ }@H_403_1@ else@H_403_1@ {@H_403_1@ for($i=0; $i< $len; ++$i)@H_403_1@ {@H_403_1@ rank(substr($base,$i).substr($base,$i+1,$len-$i-1),$temp.$base[$i]);@H_403_1@ }@H_403_1@ }@H_403_1@}@H_403_1@rank('123');@H_403_1@
代码如下:
403_1@function fsRank($base,$temp=null)@H_403_1@{@H_403_1@ static $ret = array();@H_403_1@ $len = strlen($base);@H_403_1@ if($len <= 1)@H_403_1@ {@H_403_1@ //echo $temp.$base.'
';@H_403_1@ $ret[] = $temp.$base;@H_403_1@ }@H_403_1@ else@H_403_1@ {@H_403_1@ for($i=0; $i< $len; ++$i)@H_403_1@ {@H_403_1@ $had_flag = false;@H_403_1@ for($j=0; $j<$i; ++$j)@H_403_1@ {@H_403_1@ if($base[$i] == $base[$j])@H_403_1@ {@H_403_1@ $had_flag = true;@H_403_1@ break;@H_403_1@ }@H_403_1@ }@H_403_1@ if($had_flag)@H_403_1@ {@H_403_1@ continue;@H_403_1@ }@H_403_1@ fsRank(substr($base,$temp.$base[$i]);@H_403_1@ }@H_403_1@ }@H_403_1@ return $ret;@H_403_1@}@H_403_1@print '
@H_403_1@ 原文链接：https://www.f2er.com/php/26934.html';@H_403_1@ $ret[] = $temp.$base;@H_403_1@ }@H_403_1@ else@H_403_1@ {@H_403_1@ for($i=0; $i< $len; ++$i)@H_403_1@ {@H_403_1@ $had_flag = false;@H_403_1@ for($j=0; $j<$i; ++$j)@H_403_1@ {@H_403_1@ if($base[$i] == $base[$j])@H_403_1@ {@H_403_1@ $had_flag = true;@H_403_1@ break;@H_403_1@ }@H_403_1@ }@H_403_1@ if($had_flag)@H_403_1@ {@H_403_1@ continue;@H_403_1@ }@H_403_1@ fsRank(substr($base,$temp.$base[$i]);@H_403_1@ }@H_403_1@ }@H_403_1@ return $ret;@H_403_1@}@H_403_1@print '
';@H_403_1@print_r(fsRank('122'));@H_403_1@print '';@H_403_1@
