Creating Strings

簡易題敘

給你一個長度為 n(1n8)n (1 \le n \le 8) 只含小寫字母的字串s,求它全部的排列方法數,並按字典序輸出所有方法。

範例測資:

  • 輸入
aabac
  • 輸出
20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

概念講解

這題的 nn 最多到 88,所以最多會有 8!8! 種狀況,才 4032040320 種,所以用全排列枚舉窮舉每種可能是可行的!

如教學文章所述,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';
    }
}