全排列（去重和不去重）

要求对数组a[] = {1, 2, 3, 4, 4}进行全排列（去重和不去重）。

这里提供三种代码。

[TOC]

C++的next_permutation

<algorithm>中的next_permutation可实现去重的全排列
————————————————————————————

1
2
3
4
5
6
7
8
void solve(){
	do{
		for(int i = 0; i < 5; ++i){
			cout << a[i] << " ";
		}
		cout << endl;
	}while(next_permutation(a, a+n));
}

基于新数组的全排列

创建一个新数组b[]，在 b[]上进行 a[]的全排列，这里就是最原始的Dfs了；
v[]标记已经排列过的元素，避免再次排列，ans记录全排列次数
————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int k){
	if(k == n){
		for(int i = 0; i < n; ++i){
			cout << b[i] << " ";
		}
		cout << endl;
		ans++;
		return;
	}
	for(int i = 0; i < n; ++i){
        //一行代码实现去重
		if(!v[i]){
			v[i] = 1;
			b[k] = a[i];
			dfs(k+1);
			v[i] = 0;
		}
	}
}

这样的Dfs不能实现去重，如[1 2 3 4 4]会在全排列中出现两次；
激动人心时刻来临！去重只需添加一行代码，即在上面注释位置添加：
if(i>0 && a[i]==a[i-1] && !v[i-1]) continue;

原数组上进行的全排列

方法很巧妙，只在数组a[]上通过交换位置实现的全排列
————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(int k){
	if(k == n){
		for(int i = 0; i < n; ++i){
			cout << a[i] << " ";
		}
		cout << endl;
		ans++;
	}
	for(int i = k; i < n; ++i){
		{	int t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
		dfs(k+1);
		{	int t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
}

没有新数组的创建，显然这样不能实现去重，所以要去重还要借助set
反正咱也不闲麻烦，最后对a[]进行一下去重吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
set<string> s;
void to_string(string &str){//数组a[]转换为字符串str
	for(int i = 0; i < 12; ++i){
		str.insert(str.end(), a[i]+'0');
	}
}
bool isExist(){//返回true表示有重复
	string str;
	to_string(str);
	if(s.find(str) == s.end()){
		s.insert(str);
		return false;
	}
	return true;
}