開啟章節選單
Creating Strings
簡易題敘
給你一個長度為 只含小寫字母的字串s
,求它全部的排列方法數,並按字典序輸出所有方法。
範例測資:
- 輸入
aabac
- 輸出
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa
概念講解
這題的 最多到 ,所以最多會有 種狀況,才 種,所以用全排列枚舉窮舉每種可能是可行的!
如教學文章所述,next_permutation
必須在有排序過資料的情況下才能用,所以先排序這個字串:
sort(s.begin(), s.end()); //s.begin()跟s.end()就是s字串開頭跟結尾的迭代器!
因為要求排列數,所以不能每找到一個排列就輸出,要用一個變數 k
紀錄排列數、把答案存在 ans
這個 vector
裡,最後再輸出即可。
do { k++; ans.push_back(s); } while (next_permutation(s.begin(), s.end())); cout << k << '\n'; for (auto i : ans) { cout << i << '\n'; }
範例程式碼
#include <bits/stdc++.h> using namespace std; #define int long long string s; int k; vector<string> ans; signed main() { cin >> s; sort(s.begin(), s.end()); do { k++; ans.push_back(s); } while (next_permutation(s.begin(), s.end())); cout << k << '\n'; for (auto i : ans) { cout << i << '\n'; } }