इस समस्या में, हमें एक स्ट्रिंग दी जाती है और हमें उन सभी पैलिंड्रोमिक क्रमपरिवर्तनों को प्रिंट करना होता है जो उस स्ट्रिंग के वर्णों से संभव होते हैं।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट − स्ट्रिंग ='आब'
आउटपुट - अब्बा बाबा
इस समस्या को हल करने के लिए हमें स्ट्रिंग के वर्णों को लेना होगा और इन वर्णों का उपयोग करके एक-एक करके सभी पैलिंड्रोम स्ट्रिंग्स उत्पन्न करनी होंगी।
चरण 1 - जांचें कि स्ट्रिंग एक पैलिंड्रोम है या नहीं, प्रिंट करें 'संभव नहीं ' अगर नहीं।
चरण 2 - अगर यह पैलिंड्रोम बना सकता है, तो इसे आधा कर दें और स्ट्रिंग के प्रत्येक अक्षर को लेक्सिकोग्राफिक रूप से चुनें।
चरण 3 - बनाए गए क्रमपरिवर्तन के माध्यम से पार करें और सम लंबाई स्ट्रिंग के लिए आधा पक्ष उलट दें और विषम आवृत्ति के लिए, विषम वर्ण एक पैलिंड्रोम बनाने के लिए बीच में होना चाहिए।
चरण 4 - बनाए गए सभी पैलिंड्रोम को प्रिंट करें।
एल्गोरिथम को लागू करने का कार्यक्रम -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define M 26
bool isPalindrome(string str, int* freq){
memset(freq, 0, M * sizeof(int));
int l = str.length();
for (int i = 0; i < l; i++)
freq[str[i] - 'a']++;
int odd = 0;
for (int i = 0; i < M; i++)
if (freq[i] % 2 == 1)
odd++;
if ((l % 2 == 1 && odd == 1 ) || (l %2 == 0 && odd == 0))
return true;
else
return false;
}
string reverse(string str){
string rev = str;
reverse(rev.begin(), rev.end());
return rev;
}
void generatePalindromePermutation(string str){
int freq[M];
if (!isPalindrome(str, freq))
return;
int l = str.length();
string half ="";
char oddC;
for (int i = 0; i < M; i++) {
if(freq[i] % 2 == 1)
oddC = i + 'a';
half += string(freq[i] / 2, i + 'a');
}
string palindrome;
do {
palindrome = half;
if (l % 2 == 1)
palindrome += oddC;
palindrome += reverse(half);
cout<<palindrome<<endl;
}
while (next_permutation(half.begin(), half.end()));
}
int main() {
string str="abab";
cout<<"All palindrome permutations of "<<str<<" are :\n";
generatePalindromePermutation(str);
return 0;
} आउटपुट
All palindrome permutations of abab are : abba baab