A26529. 全排列
填空题
中等
知识点
题目描述
全排列
题目描述
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。
我们假设对于小写字母有‘a’ <‘b’ < ... <‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入
只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。
输出
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：
已知S=s1 s2 ... sk, T=t1 t2 ... tk，则S<T等价于，存在p(1<=p<=k)，使得 s1= t1, s2= t2,..., sp−1= tp−1, sp<tp 成立。
输入样例
abc输出样例
abc
acb
bac
bca
cab
cba参考答案
#include<iostream>
#include<cstring>
using namespace std;
char s[10];
int len;//len为s的长度
//确定第k位置的字符，并保证下标k+1~len-1是升序字符串
void arrange(int k)
{
if(k == len-1)//如果看到最后一个字符
{
cout << s << endl;//此时s就是一种排列
return;
}
for(int i = k; i < len; ++i)
{
swap(s[k], s[i]);//交换i指向的元素和第k元素，交换后s[k+1]~s[len-1]仍然是升序字符串
arrange(k+1);//确定下一个字符
}
for(int i = k; i < len-1; ++i)//数组还原
swap(s[i], s[i+1]);
}
int main()
{
cin >> s;
len = strlen(s);
arrange(0);
return 0;
}
上一题
下一题