Creating Strings

簡易題敘

給你一個長度為 $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

概念講解

這題的 $n$ 最多到 $8$，所以最多會有 $8!$ 種狀況，才 $40320$ 種，所以用全排列枚舉窮舉每種可能是可行的！

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