資料結構
網路
關係資料庫管理系統 (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 次瀏覽
