时间:2021-05-26
算法原理
如果用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>';
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了JavaScript实现数组全排列、去重及求最大值算法。分享给大家供大家参考,具体如下:1、全排列(递归)functionpermutation(
全排列输出:解法一:复制代码代码如下:#include/*递归思想:取出数组第一个元素放到最后一个元素即a[0]和a[n]交换然后一次递归a[n]个元素的全排列
全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。现以{1,2,3,4,5}为例说明如何编写全排列的递归算法。1、首先看最后两个数4,
本文实例讲述了Java基于递归解决全排列问题算法。分享给大家供大家参考,具体如下:排列问题设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{
排列和组合算法是考查递归的常见算法,这两种算法能用递归简洁地实现。本人在经过多次摸索和思考之后,总结如下,以供参考。程序代码如下:#include#includ