递归实现全排列&使用next_permutation

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