โปรแกรม C++ หาจำนวน Permutation ของสตริง

นับจำนวน permutation (การเรียงสลับ) ของสตริง โดยพิจารณาตัวอักษรซ้ำ หากสตริงมีความยาว n และตัวอักษรบางตัวซ้ำกัน จำนวน permutation = n! / (Π freq[i]!)

โค้ดตัวอย่าง

long fact(long n) {
    return (n <= 1) ? 1 : n * fact(n-1);
}

int countPermutation(string str) {
    int freq[26] = {0};
    for (char c : str) freq[c - 'a']++;
    int res = fact(str.size());
    for (int f : freq) if (f > 1) res /= fact(f);
    return res;
}

int main() {
    string s; cin >> s;
    cout << "Permutations: " << countPermutation(s);
}

ผลลัพธ์

Enter string: abbc
The number of permutations: 12

อธิบาย: abbc มี 4 ตัวอักษร (4! = 24) แต่ 'b' ซ้ำ 2 ครั้ง (2! = 2) ดังนั้น 24/2 = 12 วิธี