การจัดเรียงคำโดยไม่เปลี่ยนตำแหน่งสัมพัทธ์ของสระและพยัญชนะ?

สมมติว่าเรามีสตริงที่มีองค์ประกอบ 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