php全排列递归算法代码

2015-01-24信息快讯网

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计算排列组合的方法
PHP 过滤页面中的BOM(实现代码)
PHP遍历某个目录下的所有文件和子文件夹的实现代码
下拉列表多级联动dropDownList示例代码
php删除字符串末尾子字符,删除开始字符,删除两端字符(实现代码)
深入解析phpCB批量转换的代码示例
PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解
解析左右值无限分类的实现算法
php实现简单洗牌算法
关于PHP二进制流 逐bit的低位在前算法(详解)
基于php冒泡排序算法的深入理解
利用php递归实现无限分类 格式化数组的详解
关于尾递归的使用详解
关于PHP递归算法和应用方法介绍
PHP递归调用的小技巧讲解
PHP递归返回值时出现的问题解决办法
php排序算法(冒泡排序,快速排序)
php列出一个目录下的所有文件的代码
仿Aspnetpager的一个PHP分页类代码 附源码下载
php随机输出名人名言的代码
php生成局部唯一识别码LUID的代码
PHP实现提取一个图像文件并在浏览器上显示的代码
微博短链接算法php版本实现代码
php数据结构与算法(PHP描述) 查找与二分法查找
通过PHP的内置函数,通过DES算法对数据加密和解密
php数据结构与算法(PHP描述) 快速排序 quick sort
php数字游戏 计算24算法
php递归创建和删除文件夹的代码小结
PHP对象转换为数组函数(递归方法)
php处理斐波那契数列非递归方法
PHP 无限分类三种方式 非函数的递归调用!
php 遍历数据表数据并列表横向排列的代码
©2014-2024 dbsqp.com