เราสามารถจัดเรียงอักขระของสตริงในลำดับที่ต่างกันได้ ในที่นี้เราจะมาดูกันว่าเราจะนับจำนวนการเรียงสับเปลี่ยนได้อย่างไรจากสตริงที่กำหนด
เรารู้ว่าถ้าหนึ่งสตริงคือ 'abc' มีสามตัวอักษร; เราสามารถจัดเป็น 3 ได้! =6 วิธีที่แตกต่างกัน ดังนั้นสตริงที่มีอักขระ n ตัว เราสามารถจัดเรียงพวกมันเป็น n ได้! วิธีทางที่แตกต่าง. แต่ตอนนี้หากมีอักขระที่เหมือนกันหลายครั้ง เช่น aab จะไม่มีการเรียงสับเปลี่ยน 6 ครั้ง
- อบา
- aab
- บ้า
- บ้า
- aab
- อบา
ที่นี่ (1,6), (2, 5), (3,4) เหมือนกัน ดังนั้นจำนวนการเรียงสับเปลี่ยนคือ 3 โดยพื้นฐานแล้ว (n!)/(ผลรวมของแฟกทอเรียลของอักขระทั้งหมดที่เกิดขึ้นมากกว่าหนึ่งครั้ง)
ในการแก้ปัญหานี้ ก่อนอื่นเราต้องคำนวณความถี่ของอักขระทั้งหมด จากนั้นนับแฟกทอเรียลของ n แล้วหารด้วยผลรวมของค่าความถี่ทั้งหมดที่มากกว่า 1
โค้ดตัวอย่าง
#include<iostream>
using namespace std;
long fact(long n) {
if(n == 0 || n == 1 )
return 1;
return n*fact(n-1);
}
int countPermutation(string str) {
int freq[26] = {0};
for(int i = 0; i<str.size(); i++) {
freq[str[i] - 'a']++; //get the frequency of each characters individually
}
int res = fact(str.size()); //n! for string of length n
for(int i = 0; i<26; i++) {
if(freq[i] > 1)
res /= fact(freq[i]); //divide n! by (number of occurrences of each characters)!
}
return res;
}
main(){
string n;
cout << "Enter a number to count number of permutations can be possible: ";
cin >> n;
cout << "\nThe number of permutations: " << countPermutation(n);
} ผลลัพธ์
Enter a number to count number of permutations can be possible: abbc The number of permutations: 12
