紫书7.2.2 生成可重集的排列

Posted on | In |

输入n个数 给出这n各数的全排列（可重复）
如
1 1 1的全排列是1 1 1
1 3 4的全排列是1 3 4

1
2
3
枚举排列的两种方法
- 递归枚举
- 用STL 的next_permutation

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
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[10000];
int p[10000];
void per(int cur){
	if(cur==n){
		for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
		cout<<endl;
		return ;
	} 
	for(int i=0;i<n;i++){//遍历的p[i]元素 
	if(!i||p[i]!=p[i-1]) {//枚举的下标不重复 1,1,3 下一次 又以第二个1开头 不合理的 

		int c1=0;
		for(int j=0;j<cur;j++){
			if(a[j]==p[i]) c1++;
		}
		//a里存的已经填好的数  cur是当前位置将要填的数 
		int c2=0;
		for(int j=0;j<n;j++){
		
		if(p[i]==p[j]) c2++;} 
		if(c1<c2) 
		{
		a[cur]=p[i];
		per(cur+1);//!!!不能放在大括号后 只有满足当前位置填的数与之前不重复 才可以填下一个 
			}
		} 
	}
	
	
} 
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>p[i]; 
	per(0);
	return 0;
}