It has been 529 days since the last update, the content of the article may be outdated.

STL next_permutation函数实现

原文链接
掌握了next_permutation函数的原理:smile:

plaintext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void inline swap(char *s1,char *s2){
    char t=*s1;
    *s1=*s2;
    *s2=t;
}
/**
*反转字符串函数,s,e分别执行字符串的开始和结尾，不能反转中文 
**/
void reverse(char *s,char* e){
    for(e--;s<e;s++,e--)swap(s,e);
}

bool next_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre>=*cur)cur--,pre--;
    if(cur<=start)return false;
    
    for(cur=end-1;*cur<=*pre;cur--);//找到逆序中大于*pre的元素的最小元素 
    swap(cur,pre);
    reverse(pre+1,end);//将尾部的逆序变成正序 
    return true;
}

prev_permutation只要将上面的cur和pre作比较的地方换一下位置就行了
plaintext
1
2
3
4
5
6
7
8
9
10
bool prev_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre<=*cur)cur--,pre--;//这里符号有变化 
    if(cur<=start)return false;
    
    for(cur=end-1;*cur>=*pre;cur--);//这里符号有变化 
    swap(*cur,*pre);
    reverse(pre+1,end);
    return true;
}

例题

给出一个字符串S（可能有重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = “1312”，

输出为：

1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
Sample Input
1312
Sample Output
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211

CODE

plaintext
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool next_permutation(char *start,char *end){
    char *cur = end-1, *pre=cur-1;
    while(cur>start && *pre>=*cur)cur--,pre--;
    if(cur<=start)return false;
    
    for(cur=end-1;*cur<=*pre;cur--);//找到逆序中大于*pre的元素的最小元素 
    swap(*cur,*pre);
    reverse(pre+1,end);//将尾部的逆序变成正序 
    return true;
}

int main(){
    char s2[100];
    scanf("%s",s2);
    int n=strlen(s2);
    sort(s2,s2+n);
    do{
        puts(s2);
//        cnt++;
    }while(next_permutation(s2,s2+n));
//    printf("%d",cnt);
}

DFS

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
const int N = 10+5;
 
char ch[N];
char ans[N];
bool vis[N];
int n;
 
void dfs(int x){
	int i;
	if(x == n){ 
		printf("%s\n",ans);
	}else{
		for(int i = 0; i < n;i++){
			if(vis[i] == false){
				vis[i] = true;
				ans[x] = ch[i];
				dfs(x+1);
				vis[i]=false;
				//筛除重复数据 
				while(i < n-1 && ch[i+1]==ch[i]) i++;
			}
		}
	}
}
 
int main()
{
	scanf("%s",&ch);
	n = strlen(ch);
	sort(ch,ch+n);
	dfs(0);
	return 0;
}