pta题目：字符串的全排列
题目描述
给定一个全由小写字母构成的字符串，求它的全排列，按照字典序从小到大输出。
输入格式:
一行，一个字符串，长度不大于8。
输出格式:
输出所有全排列，每行一种排列形式，字典序从小到大。
输入样例:
在这里给出一组输入。例如：
abc
输出样例:
在这里给出相应的输出。例如：
abc
acb
bac
bca
cab
cba
分治法解决步骤
- 分解问题：将字符串分解为一个字符和剩下的部分。对于每个字符，将它放在当前排列的开头位置，然后对剩下的字符进行递归全排列。
- 递归求解：在每次递归中，将剩下的字符分解并排列，直到字符串长度为1。
- 合并结果：在递归层级返回时，汇总每一层的结果，从而得到所有排列组合。
- 去重和排序：为确保字典序输出，在进入递归之前将字符排序，并跳过重复字符。
代码
- 使用set存储结果
#include <iostream>
#include <string>
#include <algorithm>
#include <set>using namespace std;void permute(string& str, int start, set<string>& result){// 递归结束条件if (start == str.size()){ // 处理完所有字符result.insert(str);return;}for(int i = start; i < str.size(); ++i){swap(str[start], str[i]); // 交换当前i位置要固定的字符，使该位置的所有可能字符取到permute(str, start + 1, result); // 固定当前字符，递归处理后面部分swap(str[start], str[i]); // 恢复位置}
}int main() {string input;cin >> input;// 使用set存储，可以避免对重复元素的处理set<string> result;permute(input, 0, result);for(const auto &elem: result){cout << elem << endl;}return 0;
}
- 使用vector存储结果
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;void permute(string &s, int start, vector<string> &result) {// 基本情况：如果起始位置到字符串结尾，表示找到一个排列if (start == s.size()) {result.push_back(s);return;}// 使用集合来跳过重复字符for (int i = start; i < s.size(); ++i) {// 跳过重复字符if (i != start && s[i] == s[start]) continue;swap(s[start], s[i]); // 交换当前i位置要固定的字符，使该位置的所有可能字符取到permute(s, start + 1, result); // 递归求解后续字符的排列swap(s[start], s[i]); // 还原字符位置}
}int main() {string s;cin >> s;vector<string> result;sort(s.begin(), s.end()); // 确保字符串按字典序排列permute(s, 0, result);for (const auto &elem : result) {cout << elem<< endl;}return 0;
}使用两种容器的性能分析
使用 std::set 来保存元素会有一些额外的性能开销，相比于 std::vector 或其他顺序容器，主要体现在以下几个方面：
1. 存储结构
std::set：底层通常实现为红黑树（或其他平衡树），每次插入、删除和查找操作的时间复杂度为 (O(\log n))。插入时，元素会自动按照顺序排列。std::vector：底层实现为动态数组，插入、删除操作的时间复杂度为 (O(n))（在最坏情况下），但查找操作在平均情况下是 (O(1))，适合随机访问。
2. 插入和查找的性能
- 当你插入元素到
std::set时，容器会根据元素的值保持排序状态。因此，每次插入的开销相对较高，特别是对于大量元素。 - 而在
std::vector中，插入元素的开销较低，尤其是在末尾插入的情况下，因为只需简单地增加大小和复制元素。但在插入时要维护顺序（例如排序）时，就需要额外的开销。
3. 内存使用
std::set的内存开销通常比std::vector大，因为它需要存储额外的指针来维护树的结构。std::vector的内存使用更加紧凑，适合存储大量相同类型的元素。
4. 访问性能
std::set只能通过迭代器访问元素，不能像std::vector一样通过索引随机访问。这意味着访问特定元素时会更加耗时。
总结
如果你的主要需求是存储元素并自动保持它们的有序状态，且你不在意额外的性能开销，那么使用 std::set 是一个不错的选择。但如果你的应用需要频繁地进行随机访问或对大量元素进行插入/删除操作，使用 std::vector 可能会更有效率。
在很多情况下，如果不需要保持元素的唯一性和自动排序，而只是需要一个动态数组的特性，std::vector 通常会是更好的选择。你可以在使用 std::vector 后对其进行排序，虽然排序的时间复杂度是 (O(n \log n))，但在某些情况下这仍然会比使用 std::set 更高效。