資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 程式查詢給定字串的排列數
我們可以以不同的順序排列字串中的字元。 在這裡，我們將瞭解如何計算由給定字串形成的排列數。
如果一個字串為“abc”，它有三個字元； 可以將它們排列成 3! = 6 種不同的方式。因此，可以將包含 n 個字元的字串排列成 n! 種不同的方式。但是，如果存在多次出現相同的字元，例如 aab，則不會有 6 種排列。
- aba
- aab
- baa
- baa
- aab
- aba
此處 (1, 6)、(2, 5)、(3, 4) 是相同的。因此，排列數為 3。這基本上是 (n!) / (所有出現次數多於 1 的字元的階乘之和)。
為了解決這個問題，首先必須計算所有字元的頻率。然後計算 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
更新於：30-07-2019
2 千人 次圍觀
廣告