let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

QBHV - Hoán vị chữ cái

solution.md

Xem cách sinh hoán vị ở đây.

Sau đây là cách tính số hoán vị. Giả sử chuỗi đề cho là aabbbcdd, chuỗi dài 8 kí tự, a xuất hiện 2 lần, b 3 lần, c 1 lần và d 2 lần nên ta có số hoán vị là:

\[P = \frac{8!}{2! \times 3! \times 1! \times 2!}\]

Ngoài cách làm “chuẩn” như trên, ta có thể dùng hàm next_permutation của C++ để sinh hoán vị, vừa sinh vừa đếm như trong code stl.cpp ở dưới.

main.cpp
Open in Github • Download 
#include <iostream>
#include <algorithm>
using namespace std;

void permute(string &a) {
    int n = a.size();
    while (true) {
        cout << a << '\n';
        int k, l;
        for (k = n-2; k>=0; k--) if (a[k] < a[k+1]) break;
        if (k<0) break;
        for (l = n-1; l>k; l--) if (a[k] < a[l]) break; 
        swap(a[k], a[l]);
        for (int i=k+1, j=n-1; i<j; i++, j--) swap(a[i], a[j]);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;

    sort(s.begin(), s.end());

    int res = 1;
    for (int i=1; i<=(int)s.size(); i++) res *= i;
    for (int i=1, c = 1; i<(int)s.size(); i++) {
        if (s[i] == s[i-1]) c++, res /= c;
        else c = 1;
    }
    cout << res << '\n';

    permute(s);
    return 0;
}
stl.cpp
Open in Github • Download 
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;

    sort(s.begin(), s.end());
    string res;
    int count = 0;
    do {
        count++;
        res += s;
        res += '\n';
    } while(next_permutation(s.begin(), s.end()));

    cout << count << '\n';
    cout << res;
    return 0;
}
Comments