C/C++递归实现全排列
2023-02-26 09:48:10 时间
前言
本文介绍如何用递归实现全排列。
全排列
参考题目:递归实现排列型枚举
两种方法,一是枚举每个位置,看每个位置能放哪些数。以A33为例,同是第一个位置,可以放1、2、3,三种元素。
二是枚举每个数,看每个数能放在哪些位置。即同是元素1,可以放在第一、第二、第三的位置上。
两种方法的思维和代码极其相似,本文展示第一种方法。
首先,我们创建一个数组arr,用来保存每个位置的数。
int arr[10] = { 0 };//保存已被固定的数
对于第一个位置arr【0】来说,有三种选择,分别是1、2、3,在每种选择的前提下,进行第二个位置的选择。
因为我们在固定第一个位置时已经用掉了一个数,所以在固定第二个位置arr【1】时,就不能再次使用这个数。
于是,我们创建一个数组used,利用哈希表的思想,保存每个数是否被用过。
int used[10] = { 0 };// 判断一个数是否被用过,用过则为1,没用过则为0
比如说,当我们arr【0】被固定为数字1,那么就让used【1】++,当我们进行第二、三个位置的固定时,先检测used【要固定的数】是否为0,是0才可以使用。
为了没有遗漏,我们要保证每一个位置都要对三个数进行遍历,一旦某个数可以用,就马上固定它,且每个位置的遍历顺序必须一致。
以上也是博主理解的为什么递归算法又叫深度优先搜索的原因。
深度,在本题中是代表遍历的顺序必须一致,要么从前往后,要么从后往前,只有这样才可以从一开始就一条路走到最深,才可以没有遗漏情况。
优先,在本题中是代表在每个位置对数据进行遍历的时候,只要这个数能用,就马上使用,以保证没有遗漏。
详细代码及注释如下:
//枚举每个位置放不同的数
int arr[10] = { 0 };//保存已被固定的数
int used[10] = { 0 };// 判断一个数是否被用过,用过则为1,没用过则为0
void f(int n,int h)
{
if (n == h)//如果三个数都被固定好了,则打印,可以先略过打印部分
{
int i = 0;
for (i = 0; i < h; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return;
}
int i = 0;
for (i = 0; i < h; i++)
{
if (used[i + 1] == 0)//此语句代表i+1这个数还没被用过
{
used[i + 1]++;//没被用过就马上使用它
arr[n] = i + 1;
f(n + 1,h);
used[i + 1]--;//在一种情况下的分支结束后,到另一种情况时,需要恢复原样
}
}
}
int main()
{
int h = 0;
scanf("%d", &h);
f(0,h);
return 0;
}
感谢您的阅读与耐心~
相关文章
- 我的PHP缓存类Cache 2.0版发布
- PHP5.3.9发布
- 分享一个简单的PHP分页类源码
- 一个非常简单的PHP网站首页静态化方案
- 修改Linux用户使用资源限制ulimit
- 分享一个支持UTF-8的PHP字符串截取函数
- Linux防火墙应用
- Linux系统中自动备份MySQL数据库的Shell脚本
- 2011年最热门的PHP开源项目回顾
- 一段用于检测PHP Hash漏洞的代码
- 让Linux中的SCP远程复制不再需要输入密码
- PHP-FPM启动报“fpm_unix_conf_wp(), line 124”错误解决方法
- 修复PHP 5.2.x的Hash漏洞
- 开源的企业级Linux:CentOS 5.8发布
- PHP 5.4 正式版发布,最后一个支持Windows XP/2003的版本
- Linux查看CPU、内存和机器型号等硬件信息
- 为PHP加装eAccelerator方法
- Nginx + PHP(FastCGI)安装配置笔记
- 用PHP获取客户端真实IP的函数代码分享
- Linux下的NFS配置方法