Jquery中文网 www.jquerycn.cn
Jquery中文网 >  脚本编程  >  php  >  正文 php全排列的递归算法的代码

php全排列的递归算法的代码

发布时间:2015-03-05   编辑:www.jquerycn.cn
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而生成。
 

复制代码 代码如下:
<?php
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';上面方法却有重复。
略作修改,加个判断重复的标志,问题解决。
 

复制代码 代码如下:
<?php
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全排列的递归算法的代码
php递归示例 php递归函数代码
php数组全排列的非递归算法的实例代码
一文了解Python中的递归
PHP全排列算法实现程序代码
排序算法—归并排序【附代码】
php写的递归列出所有文件和目录的函数
javascript解三阶幻方谜题
php递归创建目录小例子
PHP递归算法实例解析

关键词: php递归算法  php数组  递归算法   
[关闭]