贵阳微信网站制作,html的软件,移动网站开发公司,温州高端网站建设公司题目链接#xff1a;
全排列https://www.nowcoder.com/share/jump/437195121692001512368
描述
给定一个由不同的小写字母组成的字符串#xff0c;输出这个字符串的所有全排列。 我们假设对于小写字母有a b ... y z#xff0c;而且给定的字符串中的字…题目链接
全排列https://www.nowcoder.com/share/jump/437195121692001512368
描述
给定一个由不同的小写字母组成的字符串输出这个字符串的所有全排列。 我们假设对于小写字母有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成立。 每组样例输出结束后要再输出一个回车。
示例1
输入
abc
输出
abc
acb
bac
bca
cab
cba
方法一 递归
思路
定义递归函数 generatePermutations其中参数 prefix 表示当前已生成的前缀参数 remaining 表示剩余的字符。如果剩余字符串只有一个字符将前缀和剩余字符拼接输出。否则遍历剩余字符分别将当前字符作为前缀的一部分然后递归调用生成剩余部分的全排列。在 main 函数中读入输入的字符串调用递归函数生成全排列。
源代码
#includeiostream
using namespace std;// 递归函数用于生成字符串的全排列
void generatePermutations(string prefix, string remaining) {if (remaining.size() 1) {// 如果剩余字符串只有一个字符将前缀和剩余字符拼接输出cout prefix remaining endl;return;}// 遍历剩余字符分别将当前字符作为前缀的一部分继续递归生成全排列for (int i 0; i remaining.size(); i) {string newPrefix prefix remaining[i]; // 当前字符作为前缀的一部分string newRemaining remaining; // 拷贝剩余字符串newRemaining.erase(i, 1); // 删除当前字符得到新的剩余字符串generatePermutations(newPrefix, newRemaining); // 递归调用生成全排列}
}int main() {string s;cin s; // 输入字符串generatePermutations(, s); // 调用递归函数生成全排列return 0;
}方法二 使用内置全排列函数
next_permutation 函数的作用
next_permutation 是 C 标准库中的一个函数用于生成给定序列的下一个排列以字典序的方式。如果当前排列是字典序的最后一个排列next_permutation 返回 false否则返回 true 并生成下一个排列。在生成下一个排列时会将当前排列修改为下一个排列。next_permutation 函数接受两个迭代器作为参数表示需要生成排列的范围。
源代码
#include iostream
#include algorithm // 包含了 sort 和 next_permutation 函数
using namespace std;int main() {string s;while (cin s) { // 循环读取输入的字符串cout s endl; // 输出初始字符串sort(s.begin(), s.end()); // 将字符串按照字典序排序// 使用 next_permutation 生成剩余的全排列并输出for (; next_permutation(s.begin(), s.end());) {cout s endl;}cout endl; // 每组样例输出结束后输出一个回车}return 0;
}提交结果
