总时间限制: 1000ms 内存限制: 65536kB
描述
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入
输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。
输出
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：
已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。
样例输入
abc
样例输出
abc
acb
bac
bca
cab
cba
Code
#include <bits/stdc++.h>
using namespace std;
void f(array<char, 6> a, int n, int flag, int select, array<char, 6> res) {
array<char, 6> b;
if(flag == 0) {
for(int i = 0; i < n; i++) cout << res[i];
cout << endl;
return;
}
for(int i = 0, j = 0; i <= flag; i++) if(i != select) b[j++] = a[i];
for(int i = 0; i < flag; i++) {res[n-flag] = b[i]; f(b, n, flag-1, i, res);}
}
int main() {
string st;
cin >> st;
array<char, 6> a, res;
for(int i = 0; i < st.size(); i++) a[i] = st[i];
for(int i = 0; i < st.size(); i++) {
res[0] = a[i];
f(a, st.size(), st.size()-1, i, res);
}
}
测试用例
用例1
abc
输出
abc
acb
bac
bca
cab
cba
用例2
ab
输出
ab
ba
用例3
abcd
输出
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
碎碎念
有时候，我感觉递归更像是美化后的n重循环
