算法--生成1~n的排列

在暴力求解法中，我们常常要用上枚举一些简单内容以便方便获得解，若要输出整数n的前n个整数的全排列，则按字典序输出为：

（1，2，3），（1，3，2），（2，1，3），（2，3，1），（3，1，2），（3，2，1）。

从中我们似乎发现了一些规律：先输出以1开头的排列，再输出以2开头的排列，然后是3；而在以1开头的排列中，1的后一位又是按从小到大的顺序出现，这似乎有些递归的联系。

事实上，我们分析一下生成排列的全过程，就会发现有一定递归的规律：

这不就是一棵树嘛？确实，由于这棵树能展现递归函数的调用过程，所以也称之为----解答树。

现在，根据解答树我们可以开始构造递归函数了：  定义一个大小等于待排列元素数目的数组，据解答树特点，可用DFS方式逐层深入给数组填空，然后由数组大小作为递归边界，并且在赋值时注意判断不可重复。

代码如下

#include<cstdio>
#include <cstdlib>
using namespace std;

void permutation(int *a,int n,int cur){
	if(cur==n){
		for(int i=0;i<n;i++)printf("%d ",a[i]);printf("\n");
	}
	else {
		for(int j=1;j<=n;j++){
			int ok=1;
			for(int k=0;k<cur;k++){			
				if(a[k]==j){
					ok=0;break;
				}
			}
			if(ok){
				a[cur]=j;
				permutation(a,n,cur+1);
			}			
		}
	}
}
int main(){
	int n;
	scanf("%d",&n);
	int *a=new int[n]; 
	permutation(a,n,0); 
}