문자열의 문자를 다른 순서로 정렬할 수 있습니다. 여기서 우리는 주어진 문자열에서 형성될 수 있는 순열의 수를 계산하는 방법을 볼 것입니다.
하나의 문자열이 'abc'라면 우리는 알고 있습니다. 세 개의 문자가 있습니다. 우리는 그들을 3으로 정렬할 수 있습니다! =6가지 다른 방법. 따라서 n개의 문자가 있는 문자열을 n으로 정렬할 수 있습니다! 다른 방법들. 그러나 이제 aab와 같이 동일한 문자가 여러 번 존재하면 순열이 6개가 되지 않습니다.
- 아바
- 아아브
- 바아
- 바아
- 아아브
- 아바
여기서 (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