Chúng ta có thể sắp xếp các ký tự của một chuỗi theo thứ tự khác nhau. Ở đây, chúng ta sẽ thấy cách chúng ta có thể đếm số lượng hoán vị có thể được hình thành từ một chuỗi đã cho.
Chúng tôi biết rằng nếu một chuỗi là 'abc'. Nó có ba ký tự; chúng ta có thể sắp xếp chúng thành 3! =6 cách khác nhau. Vì vậy, một chuỗi có n ký tự, chúng ta có thể sắp xếp chúng thành n! những cách khác. Nhưng bây giờ nếu có các ký tự giống nhau xuất hiện nhiều lần, như aab, thì sẽ không có 6 hoán vị.
- aba
- aab
- trừu kêu
- trừu kêu
- aab
- aba
Ở đây (1,6), (2, 5), (3,4) giống nhau. Vì vậy, ở đây số hoán vị là 3. Về cơ bản, đây là (n!) / (Tổng các giai thừa của tất cả các ký tự xảy ra nhiều hơn một lần).
Để giải quyết vấn đề này, đầu tiên chúng ta phải tính toán tần số của tất cả các ký tự. Sau đó đếm giai thừa của n, rồi chia nó bằng cách tính tổng của tất cả các giá trị tần số lớn hơn 1.
Mã mẫu
#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);
} Đầu ra
Enter a number to count number of permutations can be possible: abbc The number of permutations: 12