假设我们有一个包含 n 个元素的字符串 (n < 10)。我们必须找到在不改变元音和辅音相对位置的情况下可以排列字符串的多种方式。
方法很简单。我们必须计算给定字符串中元音和辅音的数量,然后我们必须找到仅可以排列元音的方式有多少种,然后找到仅排列辅音的方式的数量,然后将这两个结果相乘得到总路数。
算法
arrangeWayCount(str)
'Begin
define an array ‘freq’ to store frequency.
count and place frequency of each characters in freq array. such that freq[‘0’] will hold
frequency of letter ‘a’, freq[1] will hold frequency of ‘b’ and so on.
v := number of vowels, and c := number of consonants in str
vArrange := factorial of v
for each vowel v in [a, e, i, o, u], do
vArrange := vArrange / factorial of the frequency of v
done
cArrange := factorial of c
for each consonant con, do
cArrange := cArrange / factorial of the frequency of con
done
return vArrange * cArrange
End
示例
'#include <iostream>
using namespace std;
long long factorial(int n){
if(n == 0 || n == 1)
return 1;
return n*factorial(n-1);
}
long long arrangeWayCount(string str){
long long freq[27] = {0}; //fill frequency array to 0
int v = 0, c = 0;
for (int i = 0; i < str.length(); i++) {
freq[str[i] - 'a']++;
if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
v++;
}else
c++;
}
long long arrangeVowel;
arrangeVowel = factorial(v);
arrangeVowel /= factorial(freq[0]); // vowel a
arrangeVowel /= factorial(freq[4]); // vowel e
arrangeVowel /= factorial(freq[8]); // vowel i
arrangeVowel /= factorial(freq[14]); // vowel o
arrangeVowel /= factorial(freq[20]); // vowel u
long long arrangeConsonant;
arrangeConsonant = factorial(c);
for (int i = 0; i < 26; i++) {
if (i != 0 && i != 4 && i != 8 && i != 14 && i != 20)
arrangeConsonant /= factorial(freq[i]); //frequency of all characters except vowels
}
long long total = arrangeVowel * arrangeConsonant;
return total;
}
main() {
string str = "computer";
long long ans = arrangeWayCount(str);
cout << "Possible ways to arrange: " << ans << endl;
}
输出
'Possible ways to arrange: 720