递归实现全排列&使用next_permutation

举报
野猪佩奇996 发表于 2022/01/23 00:29:29 2022/01/23
【摘要】 文章目录 1.递归版2.STL—使用next_permutation()3.其他方法 1.递归版 栗子:对1、2、3三个数字进行全排列,并按照字典序从小到大的顺序进行输出1~n的全排列...

1.递归版

栗子:对1、2、3三个数字进行全排列,并按照字典序从小到大的顺序进行输出1~n的全排列。

【思路】
递归角度,如果把问题描述成“输出1~n这n整数的全排列”——将原问题分为若干子问题:“输出以1开头的全排列”、“输出以2开头的全排列”、“输出以3开头的全排列”。。。“输出以n开头的全排列”。

【做法】
数组P——存放当前的排列;
数组hashtable[x]——为true时即整数x已经在数组P中。

(1)按顺序将P数组的第1到n位中填入数字,假设填好了P[1]~P[index-1],
(2)现在正准备P[index]——枚举1~n,如果当前枚举的数字x在前面的P[1] ~ P[n-1]中(即hashtable[x]=0),则将x填入P[index]——同时将hashtable[x]=1;
(3)递归:处理P的第index+1位;
(4)递归完成时(即已经处理完P[index]为x的子问题,需要还原状态)——将hashtable[x]设为0(即整数x不在数组P中),以便让P[index]填下一个数字

递归边界
当index达到n+1时,说明P的第1~n位都已填好了,即可以把数组P输出——表示生成了一个排列,然后直接return。

#include<stdio.h>
#include<stdlib.h>
const int maxn=11;
//P为当前排列,hashtable记录整数x是否已经在P中
int n,P[maxn],hashtable[maxn]={false};
//当前处理排列的第index号位
void generateP(int index){
	if(index==n+1){//递归边界,已经处理完排列的1~n位
		for(int i=1;i<=n;i++){
			printf("%d",P[i]);//输出当前排列
		}
		printf("\n");
		return;
	}
	for(int x=1;x<=n;x++){//枚举1~n,试图将x填入P[index]
		if(hashtable[x]==false){//如果x不在P[0]~P[index-1]中
			P[index]=x;//令P的第index为x,即把x加入当前排列
			hashtable[x]=true;//记x已在P中
			generateP(index+1);//处理排列的第index+1号位
			hashtable[x]=false;//已处理完P[index]为x的子问题,还原状态
		}
	}
}
int main(){
	n=3;//欲输出1~3的全排列
	generateP(1);//从P[1]开始填
	//return 0;
	system("pause");
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

个人感觉初学者最难理解的是递归体中的最后一步,即已处理完P[index]为x的子问题,需要还原状态(相当于一个清空原来的P数组的过程);
初学者理解递归的好方法是在VS上对递归边界和递归体分别设置一个断点调试康康

2.STL—使用next_permutation()

利用#include< algorithm >头文件的next_permutation()函数.

#include <iostream>
#include <algorithm>
using namespace std;
int sum=0;
int main()
{
	int a[6]={1,2,3}; 
	do{
		for(int i=0;i<3;i++)
			cout<<a[i];
		cout<<endl;
		sum++;
	}while(next_permutation(a,a+3));
	cout<<sum;
	system("pause");
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

(1)使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false,这样会方便退出循环;
(2)使用do…while语句而不使用while语句是因为序列1 2 3本身也需要输出,而如果用while语句会直接跳到下一个序列(1 3 2)再输出(即少了一个1 2 3)。
在这里插入图片描述

3.其他方法

其他方法可以参考大佬博客的两种方法(用了交换思想)。

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/112311719

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。