1384 全排列

 

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

输出为：

 

1123

1132

1213

1231

1312

1321

2113

2131

2311

3112

3121

3211

Input

输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）

Output

输出S所包含的字符组成的所有排列

Input示例

1312

Output示例

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

 

两种方法， 一种深搜（dfs）：假设字符串长度为 n，可以构建一个图途中有 n 点（编号分别为1，2，...n），每个点都可以到达另外的 n-1 个点， 全排列的结果也就是以每个点为起点遍历所有点的路径方法。

这种方法在这道题需要需要的注意的是，字符串中可能会有重复的字符，需要特别考虑。

举一个例子： 对 1234 进行排序

起点：     第一步        第二步         第三步

               2                 3                   4

               2                 4                   3

               3                 2                   4

1             3                 4                   2

               4                 2                   3

               4                 3                   2

起点为 2， 3， 4 时与1类似，  其实这个图有树状图效果更好，没好的画图软件，以后有了可能会补上。           

第二种方法：用库函数，更简单方便。

 

方法一代码：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 15;
bool vis[N];  void DfsForKinds(char a[],char b[],int k, int n) {if(k == n) {b[n] = '\0';cout << b << endl;return ;}for(int i=0; i<n; i++) {if(vis[i])continue;vis[i] = 1;b[k] = a[i];DfsForKinds(a, b, k+1, n);vis[i] = 0;int j=i+1;while(j<n && a[j]==a[i]) { // 处理重复字符j++; i++;}}
}int main()
{char a[N], b[N];memset(vis, 0, sizeof(vis)); cin >> a;int n = strlen(a);sort(a, a+n); // 对字符串进行排序DfsForKinds(a, b, 0, n);return 0;
}

方法二代码：

next_permutation() 函数， 头文件 <algorithm>

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 15;
char a[15];
char b[15];int main()
{cin >> a;int len = strlen(a);sort(a, a+len);strcpy(b, a);cout << a << endl;do{if(strcmp(a, b) != 0)cout << a << endl;strcpy(b, a);}while(next_permutation(a, a+len));}