解读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)
{
$len = strlen($base);
if($len <= 1)
{
echo $temp.$base.'<br/>';
}
else
{
for($i=0; $i< $len; ++$i)
{
rank(substr($base, 0, $i)tr($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)tr($base, $i+1, $len-$i-1), $temp.$base[$i]);
}
}
return $ret;
}
print '<pre>';
print_r(fsRank('122'));
print '</pre>';
-
php统计数组元素个数的方法
PHP是一种HTML内嵌式的语言,是一种在服务器端执行的嵌入HTML文档的脚本语言,语言的.风格有类似于C语言,被广泛地运用。下面是小编为大家搜索整理的php统计数组元素个数的方法,希望大家能有所收获,更多精彩内容请及时关注我们应届毕业生考试网!count():对数组中的元...
-
PHP数据类型之数组变量详解
导语:PHP是一种通用开源脚本语言。语法吸收了C语言、Java和Perl的特点,利于学习,使用广泛,主要适用于Web开发领域。下面我们来看看PHP数据类型之数组变量详解,希望对大家有所帮助。PHP中的数组实际上是一个有序图,是一种把values映射到keys的类型。一个数组实际上就...
-
PHP考试笔试题
用宝珠打扮自己,不如用知识充实自己。以下是小编为大家搜索整理的PHP考试笔试题,希望能给大家带来帮助!更多精彩内容请及时关注我们应届毕业生考试网!1、{PHP题目}标识符是变量的名称。PHP中的标识符用$+变量名来表示。标识符在PHP中遵循下列选项中的那些规则?()...
-
PHP学习10个基础知识总结
PHP学习过程中,必须要掌握基础的知识点,以下是小编为大家搜索整理的PHP学习10个基础知识总结,希望能给大家带来帮助!更多精彩内容请及时关注我们应届毕业生考试网!PHP10个小基础知识总结1,在HTML嵌入PHP脚本有三种办法:以下为引用的内容:<scriptlanguage="PHP">//嵌...