数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学回文排列的数量
字符串和数字中都可能存在排列。字符串的排列数量等于其字符个数的阶乘。在某些情况下，这些排列可能是回文的。
在本文中，我们将讨论回文排列如何在字符串中出现。我们还将使用 C++ 查找字符串中可能的回文排列的数量。
排列是从指定字符串或单词中重新排列字母或字符的数学过程。换句话说，它是按顺序重新排列对象或元素。回文是一组从开头或结尾读取时相同的字符。
给定一个字符串，我们必须找到最大可能的回文排列。
输入输出场景
给定字符串，输出是该字符串中回文排列的数量。
Input: string = "ababc" Output: 2 Input: string = "xxyyyxxzzy" Output: 30
例如，对于**字符串 = "ababc"**，我们有 2 个可能的回文排列。它们是**abcba** 和 **bacab**。
为了使字符串具有回文排列，它应该具有以下属性：
它应该具有偶数个字符频率。
如果字符频率为奇数，则只应存在一个这样的字符。例如，**ababc** 有 2 个 'a'，2 个 'b' 和 1 个 'c'。
为了创建回文序列，我们从字符串中取一半的字符，并使用它们创建可能的排列。接下来，我们反转每个结果的字符顺序，并将其附加到排列后获得的结果。
使用阶乘
我们可以通过计算字符频率的一半的阶乘来找到字符串中的回文排列。如果一半的字符重复，我们用重复频率的一半的阶乘来除。例如，字符串**“xxyyyxxzzy”** 的一半是 5。在计算字符串的一半后，x 和**y** 重复了 2 次。因此，回文排列的数量将等于**（5！）/ [（2！）*（2！）]**。结果是 30。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Calculate the factorial
long long int factorial(int n) {
long long int value = 1;
for (int i = 2; i <= n; i++) {
value *= i;
}
return value;
}
int totalCount(string str) {
vector < int > num(256);
for (char ch: str) {
num[ch]++;
}
// Taking factorial of half number of characters
long long int result = factorial(str.length() / 2);
// Check for the odd frequency
bool odd = false;
// Finding the frequency of the characters
for (int i = 0; i < 256; i++) {
int half = num[i] / 2;
if (num[i] % 2 != 0) {
if (odd) {
return 0;
}
odd = true;
}
result = result / factorial(half);
}
return result;
}
int main() {
string str = "ababc";
cout << "Number of palindromic permutations in the string " << str << " are " << totalCount(str);
return 0;
}
输出
Number of palindromic permutations in the string ababc are 2
使用频率计数
我们使用**unordered_map** 数据结构查找并存储字符串中每个字符的频率。然后，我们查找是否存在任何奇数字符。接下来，我们使用阶乘公式来获得字符串中回文排列的总数。
示例
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int totalCount(string str) {
if (str.size() == 0) {
return 0;
}
// store frequency of each character
unordered_map<char, int> freq;
for (char c: str) {
freq[c]++;
}
// Finding the odd character (if present)
int odd_value = 0;
string mid;
string start;
for (auto itr: freq){
char c = itr.first;
int x = itr.second;
if ((x & 1)){
if (++odd_value > 1) {
return 0;
}
x = x - 1;
mid = itr.first;
}
// Append x/2 characters to other half
x = x/2;
while (x--) {
start = start + c;
}
}
int num = 1;
int halfLength = start.size();
for (int j = 2; j <= halfLength; j++) {
num *= j;
}
return num;
}
int main(){
string str = "ababc";
cout << "Number of palindromic permutations in the string " << str << " are "
<< totalCount(str);
return 0;
}
输出
Number of palindromic permutations in the string ababc are 2
结论
我们讨论了查找字符串中回文排列数量的不同方法。第一种方法是使用组合的**阶乘**的简单方法。第二种方法使用**频率计数**。如果我们想打印所有可能的结果，我们可以使用**sort()** 函数和 while 循环。我们可以按字典顺序打印它们。
230 次浏览
