数据结构
网络
关系型数据库管理系统
操作系统
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 千人 次围观
广告