इस समस्या में, हमें एक स्ट्रिंग दी गई है और हमें उस स्ट्रिंग के वर्णों से संभव सभी पैलिंड्रोमिक क्रमपरिवर्तन प्रिंट करने हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं -
इनपुट - स्ट्रिंग = 'aabb'
आउटपुट - abba baab
इस समस्या को हल करने के लिए हमें स्ट्रिंग के वर्णों को लेना होगा और एक-एक करके इन वर्णों का उपयोग करके सभी पैलिंड्रोम स्ट्रिंग उत्पन्न करनी होगी।
चरण 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
