php全排列递归算法代码

yipeiwu_com5年前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 <= 1)
    {
        echo $temp.$base.'<br/>';
    }
    else
    {
        for($i=0; $i< $len; ++$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 <= 1)
    {
        //echo $temp.$base.'<br/>';
        $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, 0, $i).substr($base, $i+1, $len-$i-1), $temp.$base[$i]);
        }
    }
    return $ret;
}
print '<pre>';
print_r(fsRank('122'));
print '</pre>';

相关文章

PHP实现的CURL非阻塞调用类

本文实例讲述了PHP实现的CURL非阻塞调用类。分享给大家供大家参考,具体如下: 前面一篇《PHP实现非阻塞模式的方法》文章讲述了PHP中实现非阻塞模式,其实如果只是HTTP的话,直接用...

phpmyadmin导入(import)文件限制的解决办法

到网上搜索了一下前人的解决办法,大多数都说修改php.ini中的upload_max_filesize,但修改了这个以后,还是提示这个问题;但phpmyadmin在提示这个问题的时候,右...

php启动时候提示PHP startup的解决方法

php启动时候提示PHP startup的解决方法

最近在学习php,配置好php环境后,每次开机都有警告提示说 PHP startup。如下图: 显然这是个小问题,是关于php配置的。 解决这个问题很简单只需要在php.ini 文件中修...

深入解析PHP中逗号与点号的区别

复制代码 代码如下: echo 'abc'.'def'; //用点号连接字符串  echo 'abc','def'; //用逗号连接字符串 那么下面我们就举一些例子....

PHP中Cookie的使用详解(简单易懂)

PHP中Cookie的使用---添加/更新/删除/获取Cookie 及 自动填写该用户的用户名和密码和判断是否第一次登陆 什么是cookie 服务器在客户端保存用户的信息,比如登录名,密...