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)<BR>{<BR>    $len = strlen($base);<BR>    if($len <= 1)<BR>    {<BR>        echo $temp.$base.'<br />';<BR>    }<BR>    else<BR>    {<BR>        for($i=0; $i< $len; ++$i)<BR>        {<BR>            rank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$ba<b style="color:transparent">（、本文来源gao@!dai!ma.com搞$$代^@码网*</b><i>搞gaodaima代码</i>se[$i]);<BR>        }<BR>    }<BR>}<BR>rank('123');<BR>

不过，经多次测试运行结果，发现存在一个问题：若是存在相同的元素，则全排列有重复。
例如’122’的全排列只有三种情况：’122’、’212’、’221’；上面方法却有重复。
略修改，加个判断重复的标志，解决了问题（代码如下）：

function fsRank($base, $temp=null)<BR>{<BR>    static $ret = array();<BR>    $len = strlen($base);<BR>    if($len <= 1)<BR>    {<BR>        //echo $temp.$base.'<br />';<BR>        $ret[] = $temp.$base;<BR>    }<BR>    else<BR>    {<BR>        for($i=0; $i< $len; ++$i)<BR>        {<BR>            $had_flag = false;<BR>            for($j=0; $j<$i; ++$j)<BR>            {<BR>                if($base[$i] == $base[$j])<BR>                {<BR>                    $had_flag = true;<BR>                    break;<BR>                }<BR>            }<BR>            if($had_flag)<BR>            {<BR>                continue;<BR>            }<BR>            fsRank(substr($base, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);<BR>        }<BR>    }<BR>    return $ret;<BR>}<BR>print '<pre class="prettyprint linenums">';<BR>print_r(fsRank('122'));<BR>print '

‘;

喜欢 (0)赏

[搞代码]

分享 (0)