php全排列递归算法代码
2019/6/30 15:17:29
本文主要是介绍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>';
如果用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全排列递归算法代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28怎么把PHP程序打包?-icode9专业技术文章分享
- 2024-09-28怎么用Phar打包PHP程序?-icode9专业技术文章分享
- 2024-09-13手动在github上下载的mfpt包,怎么放到thinkphp5.0框架并正常使用-icode9专业技术文章分享
- 2024-09-05python的<class 'bytearray'>相当于php的哪个数据类型-icode9专业技术文章分享
- 2024-09-05php 导出银行卡号避免科学技术法的方法-icode9专业技术文章分享
- 2024-08-30什么样的php代码质量差被称为垃圾代码-icode9专业技术文章分享
- 2024-08-30用 PHP 调用拼多多的接口以获取订单状态消息的步骤方法和代码示例-icode9专业技术文章分享
- 2024-08-27phpunit单元测试框架的入门和使用方法介绍-icode9专业技术文章分享
- 2024-08-24PHP 中date("w") 周一是多少-icode9专业技术文章分享
- 2024-08-14thinkphp8.0获取域名或主机名方法-icode9专业技术文章分享