इस समस्या में, हमें n आकार की एक स्ट्रिंग दी गई है। और हमें सभी संभव पैलिंड्रोमिक क्रमपरिवर्तन को प्रिंट करना होगा जो कि वर्णानुक्रम में स्ट्रिंग के वर्णों का उपयोग करके उत्पन्न किया जा सकता है। यदि स्ट्रिंग प्रिंट '-1' का उपयोग करके पैलिंड्रोम नहीं बनाया गया है।
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input: string = “abcba” Output : abcba bacba
अब, इसे हल करने के लिए हमें सभी संभव पैलिंड्रोम खोजने होंगे और फिर उन्हें वर्णानुक्रम में व्यवस्थित करना होगा। या दूसरा तरीका यह हो सकता है कि स्ट्रिंग से बने लेक्सिकोग्राफ़िक रूप से पहला पैलिंड्रोम खोजा जाए। फिर अनुक्रम का क्रमिक रूप से अगला पैलिंड्रोम खोजें।
इसके लिए हम निम्नलिखित कदम उठाएंगे-
चरण 1 - स्ट्रिंग के सभी वर्णों की आवृत्ति को संग्रहीत करें।
चरण 2 - अब जांचें कि क्या स्ट्रिंग एक पैलिंड्रोम बना सकती है। यदि कोई प्रिंट नहीं है "कोई पैलिंड्रोम नहीं बनाया जा सकता है" और बाहर निकलें। अन्यथा करें -
चरण 3 - इस तर्क के आधार पर एक स्ट्रिंग बनाएं कि सम घटना वाले सभी वर्ण दूसरों से एक स्ट्रिंग और विषम घटना बनाते हैं। और हम विषम स्ट्रिंग को सम स्ट्रिंग के बीच सैंडविच करेंगे (अर्थात ईवन_स्ट्रिंग + ऑड_स्ट्रिंग + इवन_स्ट्रिंग के रूप में)।
इसका उपयोग करके हम लेक्सिकोग्राफिक रूप से पहला पालिंड्रोम पा सकते हैं। फिर समवर्ती शब्दावली संयोजनों की जांच करके अगला खोजें।
उदाहरण
अवधारणा को स्पष्ट करने के लिए कार्यक्रम -
#include <iostream>
#include <string.h>
using namespace std;
const char MAX_CHAR = 26;
void countFreq(char str[], int freq[], int n){
for (int i = 0; i < n; i++)
freq[str[i] - 'a']++;
}
bool canMakePalindrome(int freq[], int n){
int count_odd = 0;
for (int i = 0; i < 26; i++)
if (freq[i] % 2 != 0)
count_odd++;
if (n % 2 == 0) {
if (count_odd > 0)
return false;
else
return true;
}
if (count_odd != 1)
return false;
return true;
}
bool isPalimdrome(char str[], int n){
int freq[26] = { 0 };
countFreq(str, freq, n);
if (!canMakePalindrome(freq, n))
return false;
char odd_char;
for (int i = 0; i < 26; i++) {
if (freq[i] % 2 != 0) {
freq[i]--;
odd_char = (char)(i + 'a');
break;
}
}
int front_index = 0, rear_index = n - 1;
for (int i = 0; i < 26; i++) {
if (freq[i] != 0) {
char ch = (char)(i + 'a');
for (int j = 1; j <= freq[i] / 2; j++) {
str[front_index++] = ch;
str[rear_index--] = ch;
}
}
}
if (front_index == rear_index)
str[front_index] = odd_char;
return true;
}
void reverse(char str[], int i, int j){
while (i < j) {
swap(str[i], str[j]);
i++;
j--;
}
}
bool nextPalindrome(char str[], int n){
if (n <= 3)
return false;
int mid = n / 2 - 1;
int i, j;
for (i = mid - 1; i >= 0; i--)
if (str[i] < str[i + 1])
break;
if (i < 0)
return false;
int smallest = i + 1;
for (j = i + 2; j <= mid; j++)
if (str[j] > str[i] && str[j] < str[smallest])
smallest = j;
swap(str[i], str[smallest]);
swap(str[n - i - 1], str[n - smallest - 1]);
reverse(str, i + 1, mid);
if (n % 2 == 0)
reverse(str, mid + 1, n - i - 2);
else
reverse(str, mid + 2, n - i - 2);
return true;
}
void printAllPalindromes(char str[], int n){
if (!(isPalimdrome(str, n))) {
cout<<"-1";
return;
}
do {
cout<<str<<endl;
} while (nextPalindrome(str, n));
}
int main(){
char str[] = "abccba";
int n = strlen(str);
cout<<”The list of palindromes possible is :\n”;
printAllPalindromes(str, n);
return 0;
} आउटपुट
संभव पैलिंड्रोम की सूची है -
abccba acbbca baccab bcaacb cabbac cbaabc