d436 - 10098 - Generating Fast, Sorted Permutation
題目描述
題目要求對於給定的字串，產生所有可能的排列組合，並按照字典序（ASCII 碼順序）輸出這些排列。
解題思路
此題的核心在於產生字串的所有排列。程式首先對輸入字串進行排序，以確保輸出結果按照字典序排列。然後，使用 next_permutation 函數迭代產生字串的所有排列，並在每次迭代時輸出當前排列。next_permutation 函數會直接修改字串，並返回一個布林值，指示是否還有下一個排列。迴圈持續進行，直到 next_permutation 返回 false，表示所有排列都已產生。
複雜度分析
- 時間複雜度: O(n! * n)，其中 n 是字串的長度。
next_permutation的平均時間複雜度是 O(n)，而需要產生 n! 個排列。 - 空間複雜度: O(n)，主要用於儲存字串。
程式碼
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string c;
cin >> c;
while(cin >> c){
sort(c.begin(),c.end());
do{
cout << c <<"\n";
}while(next_permutation(c.begin(),c.end()));
cout << "\n";
}
/*c="ABCDEFGHI";
do{
cout << c <<"\n";
}while(next_permutation(c.begin(),c.end()));
cout << "\n";*/
}