4.1 递归和排列

递归emmm，老生常谈了，不过还要重申一个非常重要的问题即是：常规的递归实际上没有降低算法的复杂度，只是简化了代码而已。

接下来看看黑书提出的3个问题。

问题 4.1

打印n个数的全排列。

分析：用stl里面的next_permutation遍历一遍的方法就不再提了，上一章节已经用过一道例题进行说明了，至于递归的方法emmm，紫书上面提供过一种做法：

#include<cstdio>
#include<algorithm> 
using namespace std;
int ans[30],a[30]; 
void P(int n,int*x,int pos){//pos依旧表示当前递归到第几位 
	if (pos==n) {for (int i=0;i<n;i++) printf("%d ",x[i]); printf("\n");}
	else for (int i=0;i<n;i++){
		if (!i||(a[i]!=a[i-1])){//这里大家仔细一点的话可以发现,比起桶的思路
		//这里并没有对已经放入答案数组的数据进行标记,而是对准备放入答案数组的数据进行计次 
			int c1=0,c2=0;//c1表示a[i]中目前已经在答案数组中出现的次数,c2表示a[i]在整个数组中出现的次数
			for (int j=0;j<pos;j++) if (x[j]==a[i]) c1++;
			for (int j=0;j<n;j++) if (a[i]==a[j]) c2++;
		//如果c1==c2(大于显然不可能),那么代表这个数已经取完了,那么就不会再放入到答案数组中
		//然而对于a数组中相同的数,例如2,3,3,3,4,实际上并不是将3个不同位置上的3放入答案数组
		//而是将第一次出现的3三次放入答案数组中不同的位置 
			if (c1<c2) {x[pos]=a[i];P(n,x,pos+1);}
		}
	} 
}
int main(){
	int n; scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&a[i]); 
	sort(a,a+n); P(n,ans,0); return 0;
} 

紫书上代码大致的思路就是统计一个数在排列中出现的次数和在数组中出现的次数进行比较，具体不多作赘述。

黑书的方法，和回溯非常的类似，但他写的非常的烂(没有冒犯的意思，就是很烂)，非常不建议大家学习，为什么呢？

因为他连可重集都不能过(没有说胡话，我是亲自测试过的)，而且回溯法写的和大多数人的习惯也不一样。这里放一下我测试用的代码，大家自己看一下，测试一下就知道了：

#include<bits/stdc++.h>
using namespace std;
int data[]={1,1,3,3,5,6,7,8};
int num=0;
void p(int begin,int end){
	if (begin==end) {
		for (int i=0;i<=3;i++) cout<<data[i]<<" "; cout<<endl;
	}
	else for (int i=begin;i<=end;i++){
		swap(data[begin],data[i]); p(begin+1,end);
		swap(data[begin],data[i]);
	} 
} 
int main(){
	p(0,3); return 0;
}

自己测了就知道了hhh。